8.4 归并排序与基数排序

二路归并排序的过程与 O(n) 辅助空间，k 路归并的趟数；基数排序的分配与收集、MSD 与 LSD。

归并排序

归并排序与上述基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。假定待排序表含有 $n$ 个记录，则可将其视为 $n$ 个有序的子表，每个子表的长度为 1，然后两两归并，得到 $\lceil n/2 \rceil$ 个长度为 2 或 1 的有序表；继续两两归并……如此重复，直到合并成一个长度为 $n$ 的有序表为止，这种排序算法称为二路归并排序。

Merge() 的功能是将前后相邻的两个有序表归并为一个有序表。设两段有序表 A[low..mid]、A[mid+1..high] 存放在同一顺序表中的相邻位置，先将它们复制到辅助数组 B 中。每次从 B 中的两个段取出一个记录进行关键字的比较，将较小者放入 A 中，当 B 中有一段的下标超出其对应的表长（即该段的所有元素都已复制到 A 中）时，将另一段中的剩余部分直接复制到 A 中。

1void Merge(int A[], int low, int mid, int high) {
2    int i, j, k;
3    for (k = low; k <= high; k++)
4        B[k] = A[k];                     // 复制到辅助数组 B
5    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
6        if (B[i] <= B[j]) A[k] = B[i++]; // 较小者复制回 A
7        else A[k] = B[j++];
8    }
9    while (i <= mid) A[k++] = B[i++];    // 剩余部分直接复制
10    while (j <= high) A[k++] = B[j++];
11}
12void MergeSort(int A[], int low, int high) {
13    if (low < high) {
14        int mid = (low + high) / 2;
15        MergeSort(A, low, mid);
16        MergeSort(A, mid + 1, high);
17        Merge(A, low, mid, high);
18    }
19}

性能分析：

• 空间效率：Merge() 操作中，辅助空间刚好为 $n$ 个单元，所以算法的空间复杂度为 $O(n)$。
• 时间效率：每趟归并的时间复杂度为 $O(n)$，共需进行 $\lceil \log_2 n \rceil$ 趟归并，所以算法的时间复杂度为 $O(n\log_2 n)$（最好、最坏、平均都一样）。
• 稳定性：由于 Merge() 操作不会改变相同关键字记录的相对次序（B[i] <= B[j] 时取左边的），所以二路归并排序算法是一种稳定的排序算法。

基数排序

基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

假设长度为 $n$ 的线性表中每个结点 $a_j$ 的关键字由 $d$ 元组 $(k_j^{d-1}, k_j^{d-2}, \ldots, k_j^1, k_j^0)$ 组成，其中 $k_j^{d-1}$ 为最主位关键字，$k_j^0$ 为最次位关键字。为实现多关键字排序，通常有两种方法：

• **最高位优先（MSD）**法：按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列；
• **最低位优先（LSD）**法：按关键字位权重递增依次进行排序，最后形成一个有序序列。

以 $r$ 为基数的最低位优先基数排序的过程：在排序过程中，使用 $r$ 个队列 $Q_0, Q_1, \ldots, Q_{r-1}$。对 $i = 0, 1, \ldots, d - 1$，依次做一次”分配”和”收集”：

• 分配：开始时，把 $Q_0, Q_1, \ldots, Q_{r-1}$ 各个队列置成空队列，然后依次考察线性表中的每个结点 $a_j$，若 $a_j$ 的关键字 $k_j^i = k$，就把 $a_j$ 放进 $Q_k$ 队列中；
• 收集：把 $Q_0, Q_1, \ldots, Q_{r-1}$ 各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。

性能分析：

• 空间效率：一趟排序需要的辅助存储空间为 $r$（$r$ 个队列：$r$ 个队头指针和 $r$ 个队尾指针），但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为 $O(r)$。
• 时间效率：基数排序需要进行 $d$ 趟分配和收集，一趟分配需要 $O(n)$，一趟收集需要 $O(r)$，所以基数排序的时间复杂度为 $O(d(n + r))$，它与序列的初始状态无关。
• 稳定性：对于基数排序算法而言，很重要的一点就是按位排序时必须是稳定的。因此，这也保证了基数排序的稳定性。

即时练习