其他内部排序¶

插入、交换、选择都是基于比较的: 靠反复问「谁更大」排次序, 平均最快也只能到 \(O(n\log n)\).

本篇文章先看同样基于比较、但用分治把下界摸到的归并排序, 再看不比大小、靠「位数 / 取值范围」运作的基数排序和计数排序.

归并排序¶

归并排序 | Linux C 编程一站式学习

归并排序 | Hello 算法

归并排序（Merge Sort）采取分而治之（Divide-and-Conquer）, 和插入排序的增量式思路相对:

1. Divide: 把长度为 \(n\) 的序列从中点切成两半

2. Conquer: 对两半分别归并排序(树递归)

3. Combine: 把两个已经有序的子序列归并成一条

Base Case 是长度为 \(1\) (或 \(0\)) 的区间, 天然有序. 递归顺序和二叉树后序遍历一样: 先左、再右、最后处理当前区间 (这里的「处理」就是 merge).

以 \(\{5, 2, 4, 7, 1, 3, 2, 6\}\) 为例. sort(i, i) 时 start == end, 不进入 if, 直接返回 (Base Case). 真正执行顺序是后序: 先走完左子树, 再走完右子树, 最后 merge 当前区间.

完整调用树:

sort(0, 7)                         [5, 2, 4, 7, 1, 3, 2, 6]
├─ sort(0, 3)
│  ├─ sort(0, 1)
│  │  ├─ sort(0, 0)                [5]                 base
│  │  ├─ sort(1, 1)                [2]                 base
│  │  └─ merge(0, 0, 1)            [2, 5]
│  ├─ sort(2, 3)
│  │  ├─ sort(2, 2)                [4]                 base
│  │  ├─ sort(3, 3)                [7]                 base
│  │  └─ merge(2, 2, 3)            [4, 7]
│  └─ merge(0, 1, 3)               [2, 4, 5, 7]
└─ sort(4, 7)
   ├─ sort(4, 5)
   │  ├─ sort(4, 4)                [1]                 base
   │  ├─ sort(5, 5)                [3]                 base
   │  └─ merge(4, 4, 5)            [1, 3]
   ├─ sort(6, 7)
   │  ├─ sort(6, 6)                [2]                 base
   │  ├─ sort(7, 7)                [6]                 base
   │  └─ merge(6, 6, 7)            [2, 6]
   └─ merge(4, 5, 7)               [1, 2, 3, 6]
merge(0, 3, 7)                     [1, 2, 2, 3, 4, 5, 6, 7]

每次 merge 只改当前区间, 其余位置不动. 按时间顺序看整表:

初始                 5  2 | 4  7 | 1  3 | 2  6
merge(0, 0, 1)       2  5 | 4  7 | 1  3 | 2  6
merge(2, 2, 3)       2  5 | 4  7 | 1  3 | 2  6
merge(0, 1, 3)       2  4   5  7 | 1  3 | 2  6
merge(4, 4, 5)       2  4   5  7 | 1  3 | 2  6
merge(6, 6, 7)       2  4   5  7 | 1  3 | 2  6
merge(4, 5, 7)       2  4   5  7 | 1  2   3  6
merge(0, 3, 7)       1  2   2  3   4  5   6  7

两个 \(2\) 分别来自左半 (原下标 \(1\)) 和右半 (原下标 \(6\)), 相对次序见下面的稳定性说明.

算法实现¶

归并¶

两个有序表合成一个有序表, 只需每次取两侧当前最小者. 数组做不到「就地插缝」, 所以要一块辅助空间把两侧先拷出来 (或拷整段到 \(B[]\) 再写回).

void merge(int a[], int start, int mid, int end) {
    int n1 = mid - start + 1, n2 = end - mid;
    int left[n1], right[n2];
    int i, j, k;
    for (i = 0; i < n1; i++)
        left[i] = a[start + i];
    for (j = 0; j < n2; j++)
        right[j] = a[mid + 1 + j];
    i = j = 0;
    k = start;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j])   /* 相等取左, 保证稳定 */
            a[k++] = left[i++];
        else
            a[k++] = right[j++];
    }
    while (i < n1)
        a[k++] = left[i++];
    while (j < n2)
        a[k++] = right[j++];
}

设这段总长 \(n = n_1+n_2\). 拷入辅助数组 \(\Theta(n)\), 之后每确定一个最终位置走一步, 还是 \(\Theta(n)\). 定义数组本身看成 \(\Theta(1)\), 故一次 merge 是 \(\Theta(n)\).

递归排序¶

void merge_sort(int a[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        merge_sort(a, start, mid);
        merge_sort(a, mid + 1, end);
        merge(a, start, mid, end);
    }
}

时间复杂度¶

\(n=1\) 时 \(T(1)=\Theta(1)\). \(n>1\) 时要先排两半再花 \(\Theta(n)\) 合并:

把 \(T(n/2)\) 一层层展开, 得到一棵深度 \(\lg n + 1\) 的满树: 每一层的 merge 加起来都是 \(cn\), 共 \(\lg n + 1\) 层, 所以:

上下界用同一棵树就能看出来, 因此最好、最坏、平均都是 \(\Theta(n\log n)\), 与初始序列无关 (非自适应). 算法和算法评价里 \(O(n\log n)\) 的 \(\log n\) 就是这棵树的高度.

和插入排序平均 \(\Theta(n^2)\) 比, \(n\) 足够大时归并更快; 常数、低次项会被 \(n\log n\) 压过. 但 \(n\) 很小、或几乎已经有序、或内存很紧时, 直接插入往往更合适.

空间与稳定性¶

• 辅助数组 \(\Theta(n)\) (可在最外层只开一份 \(B[0..n-1]\), 不必每层都 malloc). 递归栈 \(O(\log n)\). 合计 \(O(n)\), 不是原地算法

• 稳定 (相等取左)

• 顺序表、链表都能做. 链表归并改指针即可, 不必整段搬元素, 额外空间可降到递归栈 \(O(\log n)\)

非递归的二路归并¶

递归版是自顶向下: 先切到长度为 \(1\), 再按后序 merge.

非递归版相反, 做自底向上（bottom-up）: 一开始就把每个元素看成长度为 \(1\) 的有序段, 令段长 \(width = 1, 2, 4, \ldots\), 每一趟把相邻两段交给同一份 merge.

仍用 \(\{5, 2, 4, 7, 1, 3, 2, 6\}\). 竖线隔开本趟的归并对:

初始                 5 | 2 | 4 | 7 | 1 | 3 | 2 | 6
width = 1
  merge(0, 0, 1)     2   5 | 4 | 7 | 1 | 3 | 2 | 6
  merge(2, 2, 3)     2   5 | 4   7 | 1 | 3 | 2 | 6
  merge(4, 4, 5)     2   5 | 4   7 | 1   3 | 2 | 6
  merge(6, 6, 7)     2   5 | 4   7 | 1   3 | 2   6
width = 2
  merge(0, 1, 3)     2   4   5   7 | 1   3 | 2   6
  merge(4, 5, 7)     2   4   5   7 | 1   2   3   6
width = 4
  merge(0, 3, 7)     1   2   2   3   4   5   6   7

和前面那棵递归调用树比, 最终结果一样, 但是 merge 的先后顺序不同:

• 递归: 先把左半大区间全部排完 (merge(0,1,3) 发生时, 右半的两对还没动), 再去排右半, 最后一次总 merge

• 非递归: 按层扫整表. \(width=1\) 时左右两半的四对都会先合完, 再进入 \(width=2\)

void merge_sort_iter(int a[], int n) {
    int width, i, mid, end;
    for (width = 1; width < n; width *= 2) {
        for (i = 0; i + width < n; i += 2 * width) {
            mid = i + width - 1;
            end = i + 2 * width - 1;
            if (end > n - 1)
                end = n - 1;     /* 右段可能不足 width */
            merge(a, i, mid, end);
        }
    }
}

i + width < n 保证右段至少有一个元素; 否则尾部那截已经是上一趟留下的有序段, 不必动. \(n\) 不是 \(2\) 的幂时就会走到这条边界. 例如 \(n=5\), \(\{5,2,4,7,1\}\):

width = 1    merge(0,0,1), merge(2,2,3)     2 5 | 4 7 | 1     末尾 1 无右伴
width = 2    merge(0,1,3)                   2 4 5 7 | 1
width = 4    merge(0,3,4)  (end 截成 4)     1 2 4 5 7

共 \(\lceil \log_2 n \rceil\) 趟, 每趟所有 merge 加起来仍是 \(\Theta(n)\), 所以还是 \(\Theta(n\log n)\), 与初始序列无关. 辅助数组照旧 \(O(n)\), 只是不再消耗 \(O(\log n)\) 递归栈. 稳定性完全取决于 merge 相不相等取左, 和递归版相同.

408常问「第 \(k\) 趟结束后序列长什么样」: 第 \(k\) 趟 (\(width = 2^{k-1}\)) 结束后, 相邻 \(2^k\) 长的块内部有序; 最后一块可以短于 \(2^k\).

同类分治还有快速排序: 平均也是 \(\Theta(n\log n)\), 常数通常更小, 但最坏 \(O(n^2)\), 且不稳定.

基数排序¶

基数排序（Radix Sort）是多关键字排序, 也是非比较排序: 不直接比两个记录谁大, 而是按关键字的每一位 (或每一段) 做分配 / 收集.

十进制整数可以看成 \(d\) 位关键字 \((k_{d-1},\ldots,k_0)\), 基数 \(r=10\). 常见两种扫描方向:

• LSD (最低位优先): 先个位, 再十位, 直到最高位. 每一趟必须用稳定的排序, 高位才能在低位次序之上叠上去. 408 默认考这个

• MSD (最高位优先): 先最高位分成 \(r\) 组, 再对每组递归. 实现更绕

每一趟就是一次「按当前位入队、按桶号 \(0..r-1\) 依次出队拼回」, 桶用队列实现, 其FIFO特性正好能保住稳定性.

以 \(\{32, 45, 67, 83, 43, 72, 35\}\) 做 LSD:

个位相同的 \(32\) 和 \(72\), 第二趟按十位分开, 相对次序仍来自上一趟.

算法分析¶

设 \(n\) 个记录, 基数 \(r\), 关键字位数 \(d\):

• 一趟分配扫 \(n\) 个元素 \(O(n)\), 一趟收集要过 \(r\) 个桶 \(O(n+r)\) (链式实现收集是 \(O(r)\) 次接表)

• 共 \(d\) 趟, \(T(n) = O\bigl(d(n+r)\bigr)\), 与初始序列无关

• 空间复杂度 \(O(r)\) ( \(r\) 个队头 / 队尾). 顺序表实现通常还要 \(O(n)\) 的桶空间, 所以严格意义上是 \(O(n+r)\)

• 稳定; 顺序表、链表都能做

• \(d\) 很小且 \(n\) 很大时, 可以接近线性, 优于 \(O(n\log n)\) 的比较排序. 位数很多 (大整数、长字符串) 时 \(d\) 会把优势吃掉

每位内部的稳定排序常用下面的计数排序.

计数排序¶

计数排序 | Hello 算法

计数排序（Counting Sort）面向取值范围小的整数. 思想: 数每个值出现了几次, 下标本身已经有序, 再按次数写回.

朴素写法只适合「值就是全部信息」. 要稳定、且记录还带着卫星数据, 需要前缀和: \(C[v]\) 变成「\(\leqslant v\) 的元素个数」, 从而得到值 \(v\) 在结果里的最后一个下标. 再从右往左填, 相等元素不会翻个.

/* A[i] 取值于 0..k */
void counting_sort(int A[], int n, int k) {
    int C[k + 1], B[n];
    int i;
    for (i = 0; i <= k; i++)
        C[i] = 0;
    for (i = 0; i < n; i++)
        C[A[i]]++;
    for (i = 1; i <= k; i++)
        C[i] += C[i - 1];
    for (i = n - 1; i >= 0; i--)
        B[--C[A[i]]] = A[i];
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

从左往右填也能排对, 但不稳定.

算法分析¶

• 扫 \(A\) 一次 \(O(n)\), 扫 \(C\) 一次 \(O(k)\), 再写回 \(O(n)\), \(T(n)=O(n+k)\)

• 空间复杂度 \(O(n+k)\) (B 和 C)

• 稳定; 需要按下标计数, 实质是顺序表算法

• \(k = O(n)\) 时接近线性; \(k \gg n\) (例如 \(\{1, 10^9\}\)) 时空间和时间都被 \(k\) 拖垮, 不要用

负数先整体平移到 \(\geqslant 0\); 非整型要先映射到整数. 范围未知或极大时, 回到比较排序, 或改用桶排序 (按区间分桶, 桶内再插排 / 归并, 数据均匀时平均 \(O(n)\)).

基数排序的每一位取值只有 \(r\) 种, 把上面的 \(k\) 换成 \(r\), 按「当前位」计数, 就是 LSD 的一趟.

三种算法对照¶

在 \(O(n\log n)\) 的比较排序里, 只有归并是稳定的 (快排、堆排都不稳定).