算法学习week2

Coursera算法part1课程学习记录和回顾。
第二周课程主要学习了队列堆栈的基础实现以及基本的排序算法。

1. Stack 与 Queue 的两种实现方式

• 基于数组

  • 数组的大小是初始固定的，需要在总元素个数变化时，考虑resizing调整大小，节省内存空间
  • 使用索引N记录栈顶对应位置，入栈N++，出栈N--；
  • 使用索引first last对应队列两端，入列last++，出列first--;

• 基于链表

  • 使用head记录栈顶位置，入栈时head指向新元素，head为入栈前最后一个元素的下一个元素；出栈时，则取出head指向元素，且更新head为上一元素；
  • 使用链表两端的first last节点，对应队列两端，入列更新last节点，出列更新first节点

• 删除节点时，应将原来引用的地方置为空，以便内存尽快被系统回收

2. 一些java知识备注

• Java generics 泛型编程(类似于C++的模板)

  • 应避免实际类型强转
  • 数组使用，应定义成Object后，再用泛型强转

  public class FixedCapacityStack<Item>
  {
    private Item[] s;
    private int N = 0;
    public FixedCapacityStack(int capacity)
    { s = (Item[]) new Object[capacity]; }
    ...
    ...
  }
  

• Iterable 与 Iterator

  public interface Iterable<Item>
  {
      Iterator<Item> iterator();
  }
  public interface Iterator<Item>
  {
      boolean hasNext();
      Item next();
      void remove(); //optional
  }
  

  String Iterable

• Callbacks 与 Comparable （这里说的回调有点奇怪，通常所说的回调，将函数指针作为参数进行传递调用）

  Comparable compareTo
  sort callbacks compareTo

3. 排序算法

• 选择排序，也称冒泡排序，每一轮选出剩下未排序的最小的

• 插入排序，每一次，选取一个剩下未排序元素，插入到已排序的元素中，插入操作是一步一步交换而来

• 希尔排序 shell sort，在插入排序上的改良，插入排序中插入操作需要逐步交换最终完成；希尔排序在排序时，隔h个取出元素，将这些元素进行插入排序，相当于加快了插入速度，且最终h递减到1；

• 归并排序和快速排序以及随机快速排序在第三周的课程

4. 课程作业，实现双向队列和随机化队列

没有什么难度，不过最后一些用例提示一些函数内存使用比预期的要大以及基础函数调用次数过多，性能上有些不达标吧，没有想明白 image.png