并查集 union-find

动态连通性 dynamic connectivity

将对象命名为 00 到 N−1N-1 ，使用整数作为数组索引（略去无关细节，是符号表的一个应用）

“连通”是一个等价关系：

  • 反身性：pp 连通 pp
  • 对称性：若 pp 连通 qq，则 qq 连通 pp
  • 传递性：若 pp 连通 qq，qq 连通 rr，则 pp 连通 rr

连通分量 connected components：连接在一起的最大集合

快速查找 quick find

如果 id[p]==id[q]，则 p 和 q 连通

public class QuickFindUF {
    private int[] id;

    public QuickFindUF(int N) {
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }

    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }

    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++)
            if (id[i] == pid)
                id[i] = qid; // 注意这里不能写成id[i] == id[p]，因为会更改 id[p] 的值导致后面的无法被索引到
    }
}

缺点：find() 操作速度很快，但 union() 太慢

快速合并 quick union

union 操作只需要将 pp 的根作为 qq 的根的子结点就行了，大大加快了 union 速度

public class QuickUnionUF {
    private int[] id;

    public QuickUnionUF(int N) {
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }

    private int find(int i) {
        while (i != id[i])
            i = id[i];
        return i;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        id[i] = j;
    }
}

但在最坏情况下依旧太慢了

最坏情况：树太高了，find 操作耗时过长。

快速合并改进 quick union improvement

按秩合并和路径压缩的并查集算法可优化到 N+Mα(M,N)N + M\alpha(M,N)，NN 为对象数，MM 为 UF 操作数

public class QuickUnionUF {
    private int[] id;
    private int[] sz;
    private int size;

    public QuickUnionUF(int N) {
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    private int find(int i) {
        while (i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }

    public int count() {
        return size;
    }

    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j)
            return;
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
    }
}

按秩合并 Weighted quick-union

合并时，将树较小的作为较大的根的子结点

因为只有在结点数 T2≥T1T_2 ≥ T_1 时，树高度 +1+1，所以对于 NN 个结点，树高不会超过 lg⁡N\lg N

public void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j)
        return;
    if (sz[i] < sz[j]) {
        id[i] = j;
        sz[j] += sz[i];
    } else {
        id[j] = i;
        sz[i] += sz[j];
    }
}

路径压缩 path compression

在查找 pp 的根结点时，将每个检查过的结点指向根结点

// 只添加了一行代码，将路径长度减半，已经差不多了
private int find(int i) {
    while (i != id[i]) {
        id[i] = id[id[i]];
        i = id[i];
    }
    return i;
}

// 递归做法，在回归时处理
private int find(int i) {
    if (i == id[i])
        return i;
    return id[i] = find(id[i]);
}

快速合并应用 union-find applications

渗透 Percolation模型

蒙特卡罗法 Monte Carlomethod：用计算机模拟来描述装备运用过程中随机现象

算法分析 Analysis of algorithm

观察 observation

作出“数据量-运行时间”曲线，猜测其公式

数学模型 mathematical models

将每一个操作所需时间列成表，从而计算出整个程序运行理论所需时间。

∼∼ 符号：只看最大的项

增长数量级的分类 order of growth classifications

对数级、指数级等

算法原理 theory of algorithms

最好、最坏、平均情况的考量

  • Θ\Theta 用来对算法分类
  • OO 表示上界
  • Ω\Omega 下界

内存 memory

64 位计算机使用 8 字节的指针（能访问更多地址）

一维数组：int[] 使用 4N+244N+24 字节

对象开销是 16 字节，引用 8 字节，每个对象的总使用内存必须是 8 字节的倍数

栈和队列 stack and queue

栈：先进后出；队列：先进先出

区分接口和实现的好处：更关注效率

栈 stack

public interface Stack<T> {
    void push(T item);

    T pop();

    boolean isEmpty();
}

链表实现

public class LinkedStack<T> implements Stack<T> {
    private Node first = null;

    private class Node {
        T item;
        Node next;

        Node(T i, Node n) {
            item = i;
            next = n;
        }
    }

    @Override
    public void push(T item) {
        Node oldfirst = first;
        first = new Node(item, oldfirst);
    }

    @Override
    public boolean isEmpty() {
        return first == null;
    }

    @Override
    public T pop() {
        T returnItem = first.item;
        first = first.next;
        return returnItem;
    }
}

优点是每个操作的时间较为恒定，但平摊的时间较长SLList 的发明者都不用，有利于防止突发状况

数组实现

@SuppressWarnings(value = "unchecked")
public class ArrayStack<T> implements Stack<T> {
    private T[] s;
    private int N = 0;

    public ArrayStack() {
        s = (T[]) new Object[1];
    }

    private void resize(int capacity) {
        T[] copy = (T[]) new Object[capacity];
        System.arraycopy(copy, 0, s, 0, N);
        s = copy;
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public void push(T item) {
        if (N == s.length)
            resize(2 * s.length);
        s[N++] = item;
    }

    @Override
    public T pop() {
        T returnItem = s[--N];
        s[N] = null; // 用Java要注意，Java会自动收集游离loitering的对象
        if (N > 0 && N == s.length / 4)
            resize(s.length / 2); // 防止摇摆栈
        return returnItem;
    }
}

平摊速度较快，非特殊情况建议使用这个

队列 queue

public interface Queue<T> {
    void enqueue(T item);

    T dequeue();

    boolean isEmpty();
}

链表实现

public class LinkedQueue<T> implements Queue<T> {
    private Node first, last;

    private class Node {
        T item;
        Node next;

        Node(T i, Node n) {
            item = i;
            next = n;
        }
    }

    @Override
    public boolean isEmpty() {
        return first == null;
    }

    @Override
    public void enqueue(T item) {
        Node oldlast = last;
        last = new Node(item, null);
        if (isEmpty())
            first = last;
        else
            oldlast.next = last;
    }

    @Override
    public T dequeue() {
        T returnItem = first.item;
        first = first.next;
        if (isEmpty())
            last = null;
        return returnItem;
    }
}

背包 Bag

添加一个元素到 collection 中以及迭代（顺序不重要）

import java.util.Iterator;

public class Bag<Item> implements Iterable<Item> {
    void add(Item x);

    int size();

    Iterable<Item> iterator();
}

栈和队列的应用 stack and queue applications

表达式求值的双栈算法（dijkstra's algorithm），例如 (1+((2+3)∗(4∗5)))(1+((2+3)*(4*5)))

import java.util.Stack;

public class Evaluate {
    public static void main(String[] args) {
        Stack<String> ops = new Stack<>();
        Stack<Integer> vals = new Stack<>();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            if (s.equals("("))
                ;
            else if (s.equals("+") && s.equals("*"))
                ops.push(s);
            else if (s.equals(")")) {
                String op = ops.pop();
                if (op.equals("+"))
                    vals.push(vals.pop() + vals.pop());
                if (op.equals("*"))
                    vals.push(vals.pop() * vals.pop());
            } else
                vals.push(Integer.parseInt(s));
        }
        System.out.println(vals.pop());
    }
}

本质上是计算括号内的表达式值并替换

基本排序 Elementary sort

排序介绍 sorting introduction

回调 call back：对可执行代码的引用

  • 客户端传递对象给 sort()
  • sort() 回调对象的 compareTo() 方法

Java 的实现方法是 Interface，C 语言是函数指针，c++是函数对象，python、JavaScript 是头等函数 first-class function

compareTo()实现的是全序关系 total order：

  • 反对称性：若 v≤wv ≤ w 且 w≤vw ≤ v，则 v=wv = w
  • 传递性：若 v≤wv ≤ w 且 w≤xw ≤ x，则 v≤xv ≤ x
  • 完全性：v≤wv ≤ w 和 w≤vw ≤ v 至少有一个成立

选择排序 Selection sort

思想：在第 ii 次迭代时，找到剩余的最小的索引 min，并交换 a[i] 和 a[min]

不变量 invariants：

  • ↑\uparrow 左边项的不变且保持升序排序
  • ↑\uparrow 右边项的均不小于左边的项

通过选择右边最小的项来维持其不变量。

public class Selection {
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++)
                if (less(a[j], a[min]))
                    min = j;
            exch(a, i, min);
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

选择排序使用 N22\frac{N^2}{2} 次比较和 NN 次交换

插入排序 Insertion sort

思想：在第 ii 次迭代，将 a[i] 和每一个在它左边比它大的项交换

不变量：

  • ↑\uparrow 左边（包括自己）都保持升序
  • ↑\uparrow 右边不管

通过依次将右边的项移动到应有的位置来维持不变量

public class Insertion {
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++)
            for (int j = i; j >= 1; j--)
                if (less(a[j], a[j - 1]))
                    exch(a, j, j - 1);
                else
                    break;
    }
}

对于完全随机的数组来说，插入排序平均使用 ∼14N2∼\frac{1}{4}N^2 的比较和 ∼14N2∼\frac{1}{4}N^2 的交换

证明：因为平均每次插入时移动一半的距离。

最好情况：数组已经是有序的，插入排序只使用了 N−1N - 1 的比较和 00 次交换

最坏情况：若数组反向有序排列，平均使用 ∼12N2∼\frac{1}{2}N^2 的比较和 ∼12N2∼\frac{1}{2}N^2 的交换，此时比选择排序效率低

当一个数组的逆序对 inversions ≤cN≤ cN 时，该数组是部分有序 partially sorted 的。例如在一个有序数组后接一个小数组形成的大数组。

对于部分有序的数组，插入排序只消耗线性时间。

证明：交换的次数等于逆序对数

希尔排序 Shellsort

思想：对于每 hh 个元素有序的数组每次移动多于一个位置

h-sort 的方法：插入排序，但是每次移动 hh 个单位

使用插入排序的原因：

  • 若增量大，则子数组小，插入排序可以胜任
  • 若增量小，则该数组已接近有序，插入排序效率高

该算法的正确性：一个 g-sorted 数组在 h-sort 后依旧保持 g-sorted

一个比较好的增量序列 3x+13x+1：1,4,13,39⋯1, 4, 13, 39 ⋯

public class Shell {
    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3)
            h = h * 3 + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++)
                for (int j = i; j >= h; j -= h)
                    if (less(a[j], a[j - h]))
                        exch(a, j, j - h);
                    else
                        break;
            h = h / 3;
        }
    }
}

该代码最坏情况的比较次数是 O(N32)O(N^{\frac{3}{2}})

希尔排序的优点：

  • 在数组不太大的状况下速度快
  • 代码短

洗牌 shuffling

简单做法：为每一个项生成一个随机的数字，并用生成的数字对整个数组排序

线性算法：

  • 在第 ii 次迭代中，在 [0,i][0,i](也可以是 [i,N−1][i,N-1]，但不能是 [0,N−1][0,N-1])中随机生成一个整数 rr
  • 交换 a[i] 和 a[r]
public class StdRandom {
    public static void shuffle(Object[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int r = StdRandom.uniformInt(i + 1);
            exch(a, i, r);
        }
    }
}

凸包 Convex hull

凸包是包裹所有点的最小的栅栏

应用：

  • 运动规划：两点之间的最短距离要么是直线，要么经过其间多边形障碍物的凸包
  • 最远点对：平面上一些点的最远点对在凸包上

几何性质：

  • 可以只靠逆时针旋转遍历凸包
  • 凸包顶点对于 yy 坐标最小的点 pp 的极角值递增

寻找凸包的算法之一——葛立恒扫描法 Graham's scan：

  • 选择 yy 坐标最小的点 pp
  • 对所有点按照其对于 pp 的极角大小排序
  • 依次考虑这些点，若不是逆时针旋转，则舍弃该点

判断 a→b→ca → b → c 是否为逆时针：求解 (b−a)×(c−a)(b-a) × (c-a)

import java.util.Arrays;
import java.util.Stack;

public class Point2D {
    private final double x;
    private final double y;

    public Point2D(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public static int ccw(Point2D a, Point2D b, Point2D c) {
        double area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
        if (area2 < 0)
            return -1;
        else if (area2 > 0)
            return 1;
        else
            return 0;
    }

    public static void main(String[] args) {
        Stack<Point2D> hull = new Stack<>();

        Arrays.sort(p, Point2D.Y_ORDER);
        Arrays.sort(p, p[0].BY_POLAR_ORDER);

        hull.push(p[0]);
        hull.push(p[1]);
        for (int i = 2; i < N; i++) {
            Point2D top = hull.pop();
            while (Point2D.ccw(hull.peek(), top, p[i]) <= 0)
                top = hull.pop();
            hull.push(top);
            hull.push(p[i]);
        }
    }
}

归并排序 Mergesort

归并排序 Mergesort

思想：

  • 将数组分成两半
  • 递归对两半排序
  • 合并两半

在代码前加上 assert 表明接下来想做什么，并有利于测试；在代码后加上 assert 表明该代码做了什么

public class Merge {
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid + 1, hi);

        System.arraycopy(a, lo, aux, lo, hi - lo + 1);

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                a[k] = aux[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(aux[j], aux[i]))
                a[k] = aux[j++];
            else
                a[k] = aux[i++];
        }
        assert isSorted(a, lo, hi);
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo)
            return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo; i < hi; i++)
            if (less(a[i + 1], a[i]))
                return false;
        return true;
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

assert 在生成产品时自动禁用，也可以手动启用/禁用：
java -ea MyProgram 启用
java -da MyProgram 禁用（默认）

归并排序使用最多 Nlg⁡NN \lg N 比较和 6Nlg⁡N6N \lg N 数组访问

证明：比较次数 C(N)C(N) 满足

C(N)≤C(N/2)+C(N/2)+N,N>1,C(1)=0C(N) ≤ C(N/2) + C(N/2) + N , N> 1, C(1)=0

归并排序使用了正比于 NN 的额外空间

原地 in-place 排序是指使用了 ≤clog⁡N≤ c \log N 的额外内存的算法，例如插入、选择、希尔排序。

改进 1：在小数组时使用插入排序

 private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo + CUTOFF - 1) {
        Insertion.sort(a, lo, hi);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

改进 2：跳过已排序数组

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo)
        return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    if (less(a[mid + 1], a[mid]))
        merge(a, aux, lo, mid, hi);
}

改进 3：通过交换原数组和辅助数组的角色来节省复制数组时间

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid)
            aux[k] = a[j++];
        else if (j > hi)
            aux[k] = a[i++];
        else if (less(a[j], a[i]))
            aux[k] = a[j++];
        else
            aux[k] = a[i++];
    }
}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo)
        return;
    int mid = lo + (hi - lo) / 2;
    sort(aux, a, lo, mid);
    sort(aux, a, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

自底向上归并排序 bottom-up Mergesort

思想：依次合并大小为 1,2,4,8,16⋯1,2,4,8,16 ⋯ 的子数组

public class MergeBU {
    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz *= 2)
            for (int lo = 0; lo < N - sz; lo += sz * 2)
                merge(a, lo, lo + sz - 1, Math.min(lo + sz * 2 - 1, N - 1));
    }
}

排序算法的复杂度 Sorting complexity

证明排序算法的复杂度的下界为 Nlg⁡NN \lg N：

最坏情况的由决策树高度 hh 决定，hh 高度的二叉树最多有 2h2^h 个叶结点；
对于 NN 个不同的项，有 N!N! 种排列顺序，所以最多有 N!N! 个叶结点

2h≥leaves≥N!2^h ≥ leaves ≥ N!

h≥lg⁡(N!)∼Nlg⁡Nh ≥ \lg (N!) ∼ N \lg N

所以归并排序在时间复杂度上是最优算法，但空间利用率并不一定是最优的

但在一些特殊情况下，归并排序不一定最优：

  • 输入部分有序
  • 重复值
  • 数字性质（如基数排序）

比较器 Comparator

public class Point2D {
    private final Comparator<Point2D> POLAR_ORDER = new PolarOrder();

    private class PolarOrder implements Comparator<Point2D> {
        @Override
        public int compare(Point2D o1, Point2D o2) {
            double dy1 = q1.y - y;
            double dy2 = q2.y - y;
            if (dy1 == 0 && dy2 == 0)
                ;
            else if (dy1 >= 0 && dy2 < 0)
                return -1;
            else if (dy2 >= 0 && dy1 < 0)
                return 1;
            else
                return -ccw(Point2D.this, q1, q2);
        }
    }
}

稳定性 stability

稳定性：不会改变相同值的项的顺序

插入排序和归并排序是稳定的

快速排序 Quicksort

快速排序 quicksort

思想：

  • 随机打乱数组（对于保证效率很重要）
  • 分割 Partition，对某个 jj：
    • a[j]a[j] 在原位
    • jj 左边的项都 ≤a[j]≤ a[j]
    • jj 右边的项都 $ > a[j]$
  • 递归处理左右部分
public class Quick {
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        while (true) {
            while (less(a[++i], a[lo]))
                if (i == hi) // 这一条不是多余的
                    break;
            while (less(a[lo], a[--j]))
                if (j == lo) // 其实是多余的
                    break;
            if (i >= j)
                break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (lo <= hi)
            return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
}

注意点：

  • 原地分割
  • 指针相交时结束循环
  • i 和 j 保持在边界中
  • shuffling
  • 相等的值

最坏情况下的比较次数是 ∼12N2∼ \frac{1}{2} N^2，平均比较次数 ∼2Nln⁡N∼ 2N \ln N（交换次数 ∼13Nln⁡N∼ \frac{1}{3} N \ln N）

证明：比较次数的递推公式为：

CN=(N+1)+(C0+CN−1N)+(C1+CN−2N)+⋯+(CN−1+C0N)C_N = (N+1) + (\frac{C_0 + C_{N-1}}{N}) + (\frac{C_1 + C_{N-2}}{N}) + ⋯ + (\frac{C_{N-1} + C_0}{N})

退项相减得到：

CNN+1=CN−1N+2N+1\frac{C_N}{N+1} = \frac{C_{N-1}}{N} + \frac{2}{N+1}

迭代得到：

CN=2(N+1)(13+14+⋯+1N+1)C_N = 2(N+1)(\frac 13 + \frac 14 + ⋯ + \frac{1}{N+1})

CN≈2Nln⁡N≈1.39Nlg⁡NC_N ≈ 2N \ln N ≈ 1.39N \lg N

尽管平均情况下比归并排序多 39% 比较，但在实践中因为数据移动少而比归并排序快，快速排序不是稳定的

改进 1：在小数组时使用插入排序

private static void sort(Comparable[] a, int lo, int hi) {
    if (lo <= hi + CUTOFF - 1) { // CUTOFF 为十几时能提高一定效率
        Insertion.sort(a, lo, hi);
        return;
    }
    int j = partition(a, lo, hi);
    sort(a, lo, j - 1);
    sort(a, j + 1, hi);
}

改进 2：选择数组的中位数

private static void sort(Comparable[] a, int lo, int hi) {
    if (lo <= hi)
        return;
    int m = mediaOf3(a, lo, lo + (hi - lo) / 2, hi);
    swap(a, lo, m);
    int j = partition(a, lo, hi);
    sort(a, lo, j - 1);
    sort(a, j + 1, hi);
}

选择 Selection

寻找数组中的第 kk 大/小值

思想：同快速排序，但是只在一个子数组中递归执行

public static Comparable select(Comparable[] a, int k) {
    StdRandom.shuffle(a);
    int lo = 0, hi = a.length - 1;
    while (hi > lo) {
        int j = partition(a, lo, hi);
        if (j < k)
            lo = j + 1;
        else if (j > k)
            hi = j - 1;
        else
            return a[k];
    }
    return a[k];
}

快速选择平均消耗线性时间，当然，最坏情况依旧成为平方算法

证明：类似于快速排序的分析可得

CN=2N+2kln⁡(N/k)+2(N−k)ln⁡(N/(N−k))C_N = 2N + 2k \ln (N/k) + 2 (N - k) \ln (N/(N-k))

重复的值 Duplicate keys

若不停止与分割项相等的项上，会在所有值都相等时出现 ∼12N2∼\frac 12 N^2 的时间复杂度

三路分割 3-way partition：分割时分成三部分，[lo,lt)[lo,lt) 中的均小于某个值，[lt,gt][lt,gt] 中的均等于某个值，(gt,hi](gt,hi] 中的均大于某个值。

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo)
        return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if (cmp < 0)
            exch(a, lt++, i++);
        else if (cmp > 0)
            exch(a, i, gt--);
        else
            i++;
    }
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
}

系统排序 System sorts

Java 的 Arrays.sort() 对于基本类型使用快速排序，对对象使用归并排序

快速排序优化的分割方法：

  • 小数组：中间项
  • 中数组：三项的中位数
  • 大数组：Tukey's ninther：三个元素中位数的中位数
算法名称 原地算法 稳定性 最坏情况 平均情况 最好情况 特点
选择排序 ✓✓ N22\frac{N^2}{2} N22\frac{N^2}{2} N22\frac{N^2}{2} NN 次交换
插入排序 ✓✓ ✓✓ N22\frac{N^2}{2} N24\frac{N^2}{4} NN 对 NN 较小或部分有序时有用
希尔排序 ✓✓ ?? ?? NN 代码短，比平方算法快一点
归并排序 ✓✓ Nlg⁡NN \lg N Nlg⁡NN \lg N Nlg⁡NN \lg N 保证 Nlg⁡NN \lg N，稳定
快速排序 ✓✓ N22\frac{N^2}{2} 2Nln⁡N2 N \ln N Nlg⁡NN \lg N Nlg⁡NN \lg N 的可能性保证，实践中最快
三路快速排序 ✓✓ N22\frac{N^2}{2} 2Nln⁡N2 N \ln N NN 对于有重复值的快速排序的优化
堆排序 ✓✓ 2Nlg⁡N2N \lg N 2Nlg⁡N2N \lg N Nlg⁡NN \lg N 保证 Nlg⁡NN \lg N，原地算法
??? ✓✓ ✓✓ Nlg⁡NN \lg N Nlg⁡NN \lg N Nlg⁡NN \lg N 神级算法，但目前还没有发现能实践的

优先队列 Priority queue

API 和基本实现 APIs and elementary implementations

应用：在 NN 个元素中找到最大的 MM 个元素

MinPQ<Transaction> pq = new MinPQ<>();
while (StdIn.hasNextLine()) {
    String line = StdIn.readLine();
    Transaction item = new Transaction(line);
    pq.insert(item);
    if (pq.size() > M)
        pq.delMin();
}

二叉堆 binary heap

NN 个结点的完全二叉树的高度是 ⌊lg⁡N⌋⌊ \lg N ⌋

堆顺序的二叉树：

  • 结点为值
  • 父结点的值不小于子结点的值

性质：

  • 最大的值为 a[1]，也就是二叉树的根
  • 能够使用下标在树上移动：
    • kk 的父结点是 k/2k / 2
    • kk 的子结点分别是 2k2k 和 2k+12k+1

当子结点变得比父结点大时：

  • 将子结点与父结点交换
  • 重复此过程直到恢复堆顺序

当父结点变得比子结点小时：

  • 将父结点与较大的子结点交换
  • 重复此过程直到恢复堆顺序
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;

    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public void insert(Key x) {
        pq[++N] = x;
        swim(N);
    }

    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N + 1] = null;
        return max;
    }

    private void swim(int k) {
        while (k > 1 && less(k / 2, k))
            exch(k, k / 2);
        k = k / 2;
    }

    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(j, j + 1))
                j++;
            if (!less(k, j))
                break;
            exch(k, j);
            k = j;
        }
    }
}
实现 插入 删除最大值 查询最大值
无序数组 11 NN NN
有序数组 NN 11 11
二叉堆 log⁡N\log N log⁡N\log N 11
d 叉堆 log⁡dN\log_d N dlog⁡dNd\log_d N 11
斐波那契堆 11 log⁡N\log N 11
不存在 11 11 11

不可变性的实现：

public final class Vector {
    private final int N; // 不可被覆盖
    private final double[] data;

    public Vector(double[] data) {
        this.N = data.length;
        this.data = new double[N];
        for (int i = 0; i < N; i++)
            this.data[i] = data[i];
    }
}

堆排序 heapsort

原地算法的思想：

  • 用 NN 个值创建大根堆：自底向上创建
  • 重复移除最大值
public class Heap {
    public static void sort(Comparable[] pq) {
        int N = pq.length;
        for (int k = N / 2; k >= 1; k--)
            sink(pq, k, N);
        while (N > 1) {
            exch(pq, 1, N);
            sink(pq, 1, --N);
        }
    }
}

堆排序构造使用 ≤2N≤ 2N 的比较和交换，总共使用 ≤2Nlg⁡N≤ 2N \lg N 的比较和交换

优点：最坏情况下 Nlog⁡NN \log N 的原地排序算法

缺点：

  • 不稳定
  • 内部排序比快速排序多
  • 对缓存的利用低（不是访问连续的缓存）

基本符号表 Elementary Symbol Tables

符号表 API Symbol table API

键值对的抽象：

  • 用特定的 key 插入值
  • 用 key 查询相关的值
public class ST<Key, Value> {
    ST()

    void put(Key key, Value val)

    Value get(Key key)

    void detele(Key key)

    boolean contains(Key key)

    boolean isEmpty()

    int size()

    Iterable<Key> keys()
}

惯例：

  • 值不能为 null
  • 如果 key 不存在，get() 返回 null
  • put() 用新值替换旧值

基础的实现 elementary implementation

链表序列查找：

  • 维持键值对的无序列表
  • 查找：搜索整个链表直到找到匹配
  • 插入：搜索整个链表直到找到匹配；若没有，则加到首端

在有序数组中使用二分查找：维持键值对的有序数组

public class Binary<Key, Value> {

    private Key[] keys;
    private Value[] vals;
    private int N;

    private int rank(Key key) {
        int lo = 0, hi = N - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0)
                hi = mid - 1;
            else if (cmp > 0)
                lo = mid + 1;
            else
                return mid;
        }
        return lo;
    }

    public Value get(Key key) {
        if (isEmpty())
            return null;
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0)
            return vals[i];
        else
            return null;
    }
}

但问题在于插入时需要移动所有较大的键

有序的操作 ordered operations

public interface ST<Key extends Comparable<Key>, Value> {

    Key min(); // 最大值

    Key max();// 最小值

    Key floor(Key key); // <=key的最大值

    Key ceiling(Key key);// >=key的最小值

    int rank(Key key); // 比key小的个数

    Key seleck(int k); // rank k 的数

    void deteleMin();

    void deteleMax();

    int size(Key lo, Key hi); // [lo,hi]中key的个数

    Iterable<Key> keys(Key lo, Key hi); // 有序迭代[lo,hi]的值
}

二叉查找树 Binary search tree

BST 是对称有序的二叉树

对称有序：每个结点的键：

  • 比左子树的所有键大
  • 比右子树的所有键小

在 Java 中，BST 是对根结点的引用

public class BST<Key extends Comparable<Key>, Value> {
    private Node root;

    private class Node {
        Key key;
        Value val;
        Node left, right;

        public Node(Key key, Value val) {
            this.key = key;
            this.val = val;
        }
    }

    public Value get(Key key) {
        Node x = root;
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else
                return x.val;
        }
        return null;
    }

    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
        if (x == null)
            return new Node(key, val);
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = put(x.left, key, val);
        else if (cmp > 0)
            x.right = put(x.right, key, val);
        else
            x.val = val;
        return x;
    }
}

插入/查找的效率取决于结点的深度+1，树的形状依赖于插入顺序

和快速排序的分割类似，若插入 BST 的 NN 个不同键是随机的，每次比较次数的期望是 ∼2ln⁡N∼2\ln N ，树高 ∼4.311ln⁡N∼4.311\ln N

但最坏情况下是 NN

BST 中的删除 deletion in BST

懒人法：直接将该结点的值置为 null，在搜索时忽略相等的情况，但缺点是内存利用率过低

Hibbard 删除法：

  • 没有子结点：将该结点父结点的连接设为 null
  • 一个子结点：父结点连向子结点
  • 两个子结点：
    • 找到后继 xx
    • 用 xx 替换原来的 tt，并删除 xx（tt 的右子树中的最小值）
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;

    private class Node {
        Key key;
        Value val;
        Node left, right;
        int count;

        public Node(Key key, Value val) {
            this.key = key;
            this.val = val;
            this.count = 1;
        }
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    public int size(Node x) {
        return x.count;
    }

    public void deteleMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x) {
        if (x.left == null)
            return x.right;
        x.left = deleteMin(x.left);
        x.count = 1 + size(x.left) + size(x.right);
        return x;
    }

    private Node min(Node x) {
        if (x == null)
            return null;
        while (x.left != null)
            x = x.left;
        return x;
    }

    public Node delete(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = delete(x.left, key);
        else if (cmp > 0)
            x.right = delete(x.right, key);
        else {
            if (x.right == null)
                return x.left;
            if (x.left == null)
                return x.right;

            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.count = size(x.left) + size(x.right) + 1;
        return x;
    }
}

问题在于：删除不对称——树不再是随机的 → 每次操作 N\sqrt{N}

平衡二叉搜索树 Balanced search tree

2-3 搜索树 2-3 Search tree

2-node：一个键，两个子结点 3-node：两个键，三个子结点（中间的子结点键的大小在两个键中间）

完美平衡 perfect balance：每条由根结点到 null 的链长度相同

对称顺序：中序遍历升序

插入：

  • 插入到 2-node：替换为 3-node
  • 插入到 3-node：
    • 替换为临时的 4-node
    • 将中间的 key 移动父结点中
    • 重复此操作
    • 根结点的 4-node 分裂为 3 个 2-node（只有此时树高度+1）

4-node 的分裂是局部的——常数级操作

不变量：每一个变换都维持了对称顺序和完美平衡

树高：

  • 最坏情况：ln⁡N\ln N（都是 2-nodes）
  • 最好情况：log⁡3≈6.31ln⁡N\log_3 ≈ 6.31\ln N（都是 3-nodes）

但是直接实现起来太困难，红黑树是一种简单的实现方法

红黑树 red-black BST

左倾红黑树：使用“内部”的左倾连接代替 3-node

  • 一个结点最多只有一个红链
  • 每条从根结点到 null 的链有相同数量的黑点(完美平衡)
  • 红链左倾

搜索和普通 BST 相同

public class RedBlack<Key extends Comparable<Key>, Value> {

    private final static boolean RED = true;
    private final static boolean BLACK = false;

    Node root;

    private class Node {
        Key key;
        Value val;
        Node left, right;
        boolean color;

        Node(Key key, Value val, boolean color) {
            this.key = key;
            this.val = val;
            this.color = color;
        }
    }

    private boolean isRed(Node x) {
        if (x == null)
            return false;
        return x.color == RED;
    }

    public Value get(Key key) {
        Node x = root;
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else
                return x.val;
        }
        return null;
    }

    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    private Node put(Node h, Key key, Value val) {
        if (h == null)
            return new Node(key, val, RED);
        int cmp = key.compareTo(h.key);
        if (cmp < 0)
            h.left = put(h.left, key, val);
        else if (cmp > 0)
            h.right = put(h.right, key, val);
        else
            h.val = val;
        // 简化后的三种情况
        if (isRed(h.right) && !isRed(h.left))
            h = rotateLeft(h); // 右倾改左倾
        if (isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h); // 连续两个红点的一条链（平衡4-node）
        if (isRed(h.left) && isRed(h.right))
            flipColors(h); // 分裂4-node
        return h;
    }

    // 将右倾旋转为左倾
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        return x;
    }

    // 4-node 的分裂
    private void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }
}

最坏情况下树高 ≤2lg⁡n≤ 2\lg n，因为最坏是红点和黑点轮流出现

实现 查找（最坏情况） 插入（最坏情况） 删除（最坏情况） 查找（平均） 插入（平均） 删除（平均） 顺序迭代 key 的接口
序列查找（无序列表） NN NN NN N/2N/2 NN N/2N/2 ×× equals()
二分查找（有序列表） lg⁡N\lg N NN NN lg⁡N\lg N N/2N/2 N/2N/2 ✓✓ compareTo()
BST NN NN NN 1.39lg⁡N1.39\lg N 1.39lg⁡N1.39\lg N ?? ✓✓ compareTo()
2-3 树 clg⁡Nc\lg N clg⁡Nc\lg N clg⁡Nc\lg N clg⁡Nc\lg N clg⁡Nc\lg N clg⁡Nc\lg N ✓✓ compareTo()
红黑树 2lg⁡N2 \lg N 2lg⁡N2 \lg N 2lg⁡N2 \lg N 1.00lg⁡N1.00 \lg N 1.00lg⁡N1.00 \lg N 1.00lg⁡N1.00 \lg N ✓✓ compareTo()
分离链接法 lg⁡N\lg N lg⁡N\lg N lg⁡N\lg N 3−53-5 3−53-5 3−53-5 ×× equals()
线性探查法 lg⁡N\lg N lg⁡N\lg N lg⁡N\lg N 3−53-5 3−53-5 3−53-5 ×× equals()

B 树 B-tree

B 树：泛化的 2-3 树，每个结点最多有 M−1M-1 个链

  • 根结点最少 22 链
  • 其它结点最少 M/2M/2 链
  • 外部结点保存客户的键
  • 内部结点存键的复制来指导搜索

插入：

  • 搜索新的键
  • 在底部插入
  • 在返回根结点时分裂有 MM 个链的结点

MM 和 NN 个结点的 B 树需要 log⁡M−1N∼log⁡M/2N\log_{M-1}N ∼ \log_{M/2} N 查找，因为每个内部结点都有 M/2∼M−1M/2 ∼ M-1 条链

红黑树的应用：

  • Java：TreeMap、TreeSet
  • C++STL:map、multimap、multiset

B 树：Windows 的 NTFS

BST 几何学的应用 Geometric applications of BSTs

区间查找：查找所有 k1k_1 到 k2k_2 之间的键 区间计数：所有 k1k_1 到 k2k_2 之间的键总数

几何解释：

  • 键是排列在一条线上的所有点
  • 在一维区间查找/计数点

插入：log⁡N\log N，范围计数：log⁡N\log N，范围搜索：R+log⁡NR+\log N（RR 为匹配的键数量）

线段相交 Line segment intersection

给 NN 条水平、竖直的线段，查找所有相交的

扫描线算法：竖直线从左到右扫描：

  • 按 x 坐标排序
  • 碰到水平线段的左端点：向 BST 中插入 y 坐标
  • 碰到水平线段的右端点：向 BST 中删除 y 坐标
  • 碰到竖直线段：范围查找 y 端点

本质上将二维正交线段相交转化为一维范围搜索，时间复杂度为 Nlog⁡N+RN\log N+R

k 维树 kd-tree

二维正交范围搜索：

  • 插入二维键
  • 删除二维键
  • 查找二维键
  • 范围查找
  • 范围计数

几何解释：

  • 键是平面上的点
  • 查找/计数给定的梯形的点

方格实现

  • 把空间分成 M×MM × M 的方格
  • 在每个方格里创建点的列表
  • 使用二维数组索引相关方格

时间-空间的权衡：

  • 时间：M2+NM^2 + N
  • 空间：平均每个方格 1+N/M21+N/M^2
  • 最好的选择：N×N\sqrt{N} × \sqrt{N} 的方格

团簇现象：大量点都集中在一起

使用树来递归划分二维空间

数据结构：BST，但是插入点时交替使用 x 和 y 坐标来作为键

查找矩形中的所有点：

  • 检查点是否在给定矩形内
  • 递归查找左边/下面（如果有可能落在矩形内）
  • 递归查找右边/上面（如果有可能落在矩形内）

一般情况：R+log⁡NR+\log N
最坏情况（即使树是平衡的）：R+NR + \sqrt{N}

查找最近邻居：

  • 检查结点中的点到询问的点的距离
  • 递归查找左边/下面（如果有可能有更近的点）
  • 递归查找右边/上面（如果有可能有更近的点）

一般情况：log⁡N\log N
最坏情况（即使树是平衡的）：NN

kd 树：递归把 k 维空间划分成两片空间

区间搜索树 Interval search tree

一维区间搜索：

  • 插入区间 (lo,hi)
  • 搜索区间 (lo,hi)
  • 删除区间 (lo,hi)
  • 区间相交查询：给定一个区间 (lo,hi)，在数据结构中找到所有（或一个）与 (lo,hi) 相交的区间

BST 的每一个结点储存区间 (lo,hi)

  • 用左端点作键
  • 在每个结点储存子树中最大的右端点

查找是否有与给定区间 (lo,hi) 相交的区间：

  • 如果结点处区间与询问的区间相交，返回该区间
  • 如果没有左子树，查找右子树
  • 如果左子树最大的右端点小于 lo，查找右子树
  • 否则查找左子树

矩形相交 Rectangle intersection

找到所有正交矩阵的相交

如果没有线性算法，摩尔定律无法生效

扫描线算法：

  • x 坐标决定事件
  • 左端点：使用 y 坐标插入区间搜索树
  • 右端点：移除 y 区间

本质上将二维正交矩形相交转化为一维区间搜索，时间复杂度为 Nlog⁡N+Rlog⁡NN\log N+R\log N

哈希表 Hash table

哈希表 Hash table

把物品储存在以键为索引的表中

哈希函数：计算键的索引的方法

所有 Java 的类都有一个方法 hashCode()，返回一个 32 位的 int

需求：如果 x.equals(y)，那么 x.hashCode() == y.hashCode()

最好：如果 !x.equals(y)，那么 x.hashCode() != y.hashCode()

默认实现：x 的内存

public final class String {
    // 因为String不可变，所以可以将hash值记录下来，减少计算次数
    private int hash = 0;
    private final char[] s;

    public int hashCode() {
        int h = hash;
        if (h != 0)
            return h;
        for (int i = 0; i < s.length; i++)
            h = s[i] + (h * 31);
        hash = h;
        return h;
    }
}

哈希取模：

private int hash(Key key) {
    return (key.hashCode() & 0x7fffffff) % M; // M 通常为质数或2的整数次幂
}

生日问题：在 ∼πM/2∼\sqrt{π M /2} 后两个球放在同一个仓里

赠券收集问题 Coupon Collector's Problem：在 ∼Mln⁡M∼M\ln M 后期望每个仓至少有一个球

负载均衡 Load Balance：在 MM 次后，最多的仓有 Θ(log⁡M/log⁡log⁡M)Θ(\log M / \log \log M) 个球

分离链接法 Separate Chaining

冲突：两个不同的键有相同的索引

  • 插入：在第 i 个链之前插入
  • 查找：只需要搜索第 i 个链
public class SeparateChainingHashST<Key, Value> {
    private int M = 97;
    private Node[] st = new Node[M];

    private static class Node {
        Object key;
        Object val;
        Node next;
    }

    public Value get(Key key) {
        int i = hash(key);
        for (Node x = st[i]; x != null; x = x.next)
            if (key.equals(x.key))
                return (Value) x.val;
        return null;
    }
}

查找消耗 ∼N/M∼N/M

  • MM 太大，空链太多
  • MM 太小，链太长
  • 通常选择 M∼N/5M∼N/5，操作为常数时间

线性探查法 linear probing

也称开放地址法：

  • 插入：若 i 有空，就插入；否则尝试 i+1、i+2 等
  • 搜索：查找索引 i，如果被占但不匹配，尝试 i+1、i+2 等
public class LinearProbingHashST<Key, Value> {
    private int M = 30001;
    private Value[] vals = (Value[]) new Object[M];
    private Key[] keys = (Key[]) new Object[M];

    public void put(Key key, Value val) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key)) {
                keys[i] = key;
                vals[i] = val;
                return;
            }
    }

    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (key.equals(keys[i]))
                return vals[i];
        return null;
    }
}

问题：新的键趋向于出现在大团簇的中心

Knuth 的停车问题：

  • 半满时，失配的平均数 ∼32∼ \frac 32
  • 全满时，失配的平均数 ∼πM/8∼ \sqrt{π M/8}

假设 N=αMN=αM，则查找击中的 ∼12(1+11−α)∼\frac 12(1+\frac{1}{1-α})，查找错过的 ∼12(1+1(1−α)2)∼\frac 12(1+\frac{1}{(1-α)^2})

通常选择 α∼12α ∼ \frac 12

哈希表来龙去脉 Hash table context

分离链接法：

  • 更容易实现删除
  • 效率退化良好
  • 团簇影响小

线性探查法：

  • 空间浪费少
  • 缓存表现好

其它改进版本：

双探针哈希（分离链接法的变形）：

  • 哈希到两个位置，把键插入到较短的一条链中
  • 最长链减少到 log⁡log⁡N\log \log N

双哈希（线性探查法的变形）：

  • 线性探查法，但每次跳过可变数量而不是 1
  • 对团簇效果好
  • 允许表几乎全满
  • 删除实现困难

布谷鸟哈希 Cuckoo hashing：

  • 哈希到两个位置，插入到一个位置，若被占，重新插入该位置的键到另一个位置
  • 最坏情况下查找时间为常数

哈希表：

  • 实现容易
  • 对于无序键，没有更有效的替代
  • 对于简单的键更快

BST：

  • 效率有保证
  • 支持有序操作
  • 比起 equals() 和 hashCode()，实现 compareTo()更容易

符号表应用 Symbol application

集合 Set

不同键的总和

字典客户端 dictionary clients

ip 和域名的查询

索引客户端 indexing clients

文件语境查询

稀疏向量 Sparse vector

一维向量数组表示：

  • 常数时间访问元素
  • 空间花费 ∼N∼N

符号表表示：

  • 键为索引，值为项
  • 迭代效率高
  • 空间花费和非零时成正比
public class SparseVector {
    private HashST<Integer, Double> v;

    public SparseVector() {
        v = new HashST<Integer, Double>();
    }

    public void put(int i, double x) {
        v.put(i, x);
    }

    public double get(int i) {
        if (!v.contain(i))
            return 0.0;
        else
            return v.get(i);
    }

    public Iterable<Integer> indices() {
        return v.keys();
    }

    public double dot(double[] that) {
        double sum = 0.0;
        for (int i : indices())
            sum += that[i] * this.get(i);
        return sum;
    }
}