week2: Stacks and Queues & Elementary Sorts

泛型与可迭代的数据结构

泛型

在java中实现泛型十分简单，只需定义类时在类名后加上<类型名>，然后在类中用到此类型数据时通通使用类型名修饰即可。如

public class Stack<Item> {
    private Item[] s;
    ...
}

可迭代

若想自定义的数据结构是可迭代的，那么就需要实现Iterable接口，重写iterator()方法，其会返回一个迭代器，定义如下：

// Iterable interface, built in to java
public interface Iterable<Item> {
    Iterator<Item> iterator();
}

当然，我们需要自己定义这个迭代器是如何遍历我们所写的数据结构的。java提供了Iterator接口，我们实现它即可。

// Iterator interface, built in to java
public interface Iterator<Item> {
    boolean hasNext();
    Item next();
    void remove();  // optional; use at your own risk
}

在client程序中，可以使用范围for循环来进行迭代遍历：

for (String s : stack)
    StdOut.println(s);

其等价于：

Iterator<String> i = stack.iterator();
while (i.hasNext()) {
    String s = i.next();
    StdOut.println(s);
}

基础排序算法

回调（callback）

我们的排序方法在不知道传入的数据类型是什么时，是如何在排序中比较各个元素的呢？使用回调函数。

客户程序传入需要排序的数组，我们的排序方法在比较元素时会调用该元素对象的compareTo()方法来完成比较。

即对于一个以比较元素为基础的排序方法而言，传进来的对象需自己是可比较的（Comparable），在java中就是需要实现Comparable接口，重写compareTo()方法。

// Comparable interface, built in to java
public interface Comparable<Item> {
    public int compareTo(Item that);
}

然后我们的排序方法将传进来的数组当成可比较对象的数组即可，如：

public static void sort(Comparable[] a) {
    ...
}

插入排序

在这几个基础排序算法中，我们着重讨论下插入排序。

插入排序是时间复杂度为$O(n^2)$、稳定（stable）且原地（in place）的排序算法，它在数组接近有序和数组较小时常被选用来排序。为什么呢？

  1. 数组接近有序。插入排序是每次将当前元素与前面的元素一一比较，直到找到小于等于它的元素就在该位置插入。若数组接近有序，那么插入排序比较和交换的次数就很少，能在$O(n)$的时间内完成。
  2. 数组较小。当数组较小时，插入排序是很快的，因为它是原地的（in place），没有较多的开销。此时它常用来代替归并排序（merge sort）和快速排序（quick sort），因为这两个排序的递归调用对带来额外的栈开销。

Assignment: Deques and Randomized Queues

代码见这里。在这主要说明下完成作业的几个关键点：

  1. loitering。在链表实现deque的过程中，由于有next和prev两个引用，稍有不慎就会出现loitering。以addFirst函数为例，添加一个新的first节点后，如果仅仅设置了该节点的next和prev引用，是会出现loitering的。若链表不止有这一个新增的节点，那么原来的first节点的prev应该指向它，即oldFirst.prev = first。
  2. 随机队列的dequeue函数。由于随机队列是随机删除一个元素，若用数组实现，那一下标直接就空了，如果置之不理，仍然是在后面入列，则出列操作不好实现。为了解决这一问题，我们可以交换删除元素位置的值和队尾元素的值。
  3. bonus：bonus的问题我也不会，是在论坛上了解到的方法——水塘抽样。水塘抽样是一种统计的随机算法，在这里不作探讨，不了解的朋友可以参见：Reservoir sampling（水塘抽样）。

参考