排序的基本概念

排序的定义

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

算法的稳定性。若待排序表中有两个元素 $R_i$ 和 $R_j$ ，其对应的关键字相同即 $\mathrm{ key}_i= \mathrm{ key}_j$，且在排序前 $R_i$ 在 $R_j$ 的前面，若使用某一排序算法排序后，$R_i$ 仍然在 $R_j$ 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。

注意：对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可。

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：

  1. 内部排序，是指在排序期间元素全部存放在内存中的排序；
  2. 外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。（除了关注算法时间和空间复杂度外，还要考虑如何使读写磁盘的次数更少）

一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类，后面几节会分别进行详细介绍。内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的。

插入排序

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。

直接插入排序

根据上面的插入排序思想，不难得出一种最简单也最直观的直接插入排序算法。假设在排序过程中，待排序表 L[1...n] 在某次排序过程中的某一时刻状态如下: 有序序列 L[1...i-1] ，L(i)，无序序列 L[i+1...n]

要将元素 L(i) 插入到已有序的子序列 L[1...i-1] 中，需要执行以下操作（为避免混淆，下面用 L[] 表示一个表，而用L() 表示一个元素）：

  1. 查找出 L(i) 在 L[1...i-1] 中的插入位置 k。
  2. 将 L[k...i-1] 中的所有元素依次后移一个位置。
  3. 将 L(i) 复制到 L(k)。

为了实现对 L[1...n] 的排序，可以将 L(2)~L (n) 依次插入到前面已排好序的子序列中，初始 L[1] 可以视为是一个已排好序的子序列。上述操作执行 $n-1$ 次就能得到一个有序的表。插入排序在实现上通常采用就地排序（空间复杂度为 $O(n)$ ）， 因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

下面是直接插入排序的代码，其中再次用到了我们前面提到的“哨兵”（作用相同）。

1
2
3
4
5
6
7
8
9
10
11
void InsertSort(ElemType A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {  // 依次将A[2]~A[n]插入到前面已排序序列
        if (A[i] < A[i - 1]) {  // 若A[i]关键码小于其前驱，将A[i]插入有序表
            A[0] = A[i];  // 复制为哨兵，A[0]不存放元素
            for (j = i - 1; A[0] < A[j]; --j)  // 从后往前查找待插入位置
                A[j + 1] = A[j];               // 向后挪位
            A[j + 1] = A[0];                   // 复制到插入位置
        }
    }
}

直接插入排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 $O(1)$ 。

时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了 $n-1$ 趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为 $O(n)$。

在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，为 $\sum_{i=2}^{n}i$ ，总的移动次数也达到最大，为 $\sum_{i=2}^{n}(i+1)$ 。

平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 $\frac{n^2}{4}$ 。

因此，直接插入排序算法的时间复杂度为 $O(n^2)$。

稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

注意：大部分排序算法都仅适用于顺序存储的线性表。

折半插入排序

从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：

  1. 从前面的有序子表中查找出待插入元素应该被插入的位置；
  2. 给插入位置腾出空间，将待插入元素复制到表中的插入位置。

注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。算法代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {  // 依次将A[2]~A[n]插入前面的已排序序列
        A[0] = A[i];            // 将A[i]暂存到A[0]
        low = 1;                // 设置折半查找的范围
        high = i - 1;
        while (low <= high) {        // 折半查找(默认递增有序)
            mid = (low + high) / 2;  // 取中间点
            if (A[mid] > A[0]) {
                high = mid - 1;  // 查找左半子表
            } else {
                low = mid + 1;  // 查找右半子表，保证算法稳定性
            }
        }
        for (j = i - 1; j >= high + 1; --j) {
            A[j + 1] = A[j];  // 统一后移元素，空出插入位置
        }
        A[high + 1] = A[0];  // 插入操作
    }
}

从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为 $O(n\log_{2}{n})$ ，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 $n$ ；而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为 $O(n^2)$，但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

希尔排序

从前面的分析可知，直接插入排序算法的时间复杂度为 $O(n^2)$ ，但若待排序列为“正序”时，其时间复杂度可提高至 $O(n)$，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

希尔排序的基本思想是：先将待排序表分割成若干形如 L[i,i+d,i+2d,...,i+kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序的过程如下：先取一个小于 $n$ 的步长 $d_i$ ，把表中的全部记录分成 $d_1$ 组，所有距离为 $d$ 的倍数的记录放在同一组， 在各组内进行直接插入排序；然后取第二个步长 $d_2<d_1$，重复上述过程，直到所取到的 $d_t = 1$，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列，希尔提出的方法是 $d_1=\frac{n}{2},\ d_{i+1}=\left \lfloor \frac{d_i}{2} \right \rfloor$，并且最后一个增量等于 1。

希尔排序算法的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void ShellSort(int A[], int n) {
    int d, i, j;
    // A[0]只是暂存单元，不是哨兵
    for (d = n / 2; d > 1; d = d / 2) {  // 步长变化
        for (i = d + 1; i <= n; ++i) {
            if (A[i] < A[i - d]) {  // 需将A[i]插入有序增量子表
                A[0] = A[i];        // 暂存在 A[0]
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) {
                    A[j + d] = A[j];  // 记录后移，查找插入的位置
                }
                A[j + d] = A[0];  // 插入
            }
        }
    }
}

希尔排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 $O(1)$。

时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当 $n$ 在某个特定范围时，希尔排序的时间复杂度约为 $O(n^{1.3})$。在最坏情况下希尔排序的时间复杂度为 $O(n^2)$。

稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

交换排序

冒泡排序

冒泡排序的基本思想是：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 A[i-1] > A[i]），则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”（或关键字最大的元素如石头一般下沉至水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置……这样最多做 $n-1$ 趟冒泡就能把所有元素排好序。

冒泡排序算法的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BubbleSort(ElemType A[], int n) {
    int temp;
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;  // 表示本轮冒泡是否发生了交换的标志
        for (int j = n - 1; j > i; j--) {
            if (A[j - 1] > A[j]) {
                temp = A[j - 1];  // 交换
                A[j - 1] = A[j];
                A[j] = temp;
                flag = true;
            }
        }
        if (flag == false) {
            return;  // 本次遍历后没有发生交换，说明表已经有序
        }
    }
}

冒泡排序的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 $O(1)$ 。

时间效率：当初始序列有序时，显然第一趟冒泡后 flag 依然为 false （本趟冒泡没有元素交换），从而直接跳出循环，比较次数为$n- 1$ ，移动次数为 0，从而最好情况下的时间复杂度为 $O(n)$ ；当初始序列为逆序时，需要进行 $n- 1$ 趟排序，第 $i$ 趟排序要进行 $n -i$ 次关键字的比较，而且每次比较后都必须移动元素 3 次来交换元素位置。这种情况下，比较次数= $\frac{n(n-1)}{2}$ ，移动次数 = $\frac{3n(n-1)}{2}$ 从而，最坏情况下的时间复杂度为 $O(n^2)$ ，其平均时间复杂度也为 $O(n^2)$ 。

稳定性：由于 i>j 且 A[i]=A[j] 时，不会发生交换，因此冒泡排序是一种 稳定的排序方法。

注意：冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

快速排序

快速排序的基本思想是基于分治法的：在待排序表 L[1..n] 中任取一个元素 pivot 作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分 L[1...<k-1] 和 L[k+1...n]，使得 L[1...k-1] 中的所有元素小于 pivot ， L[k+1...n] 中的所有元素大于等于 pivot ，则 pivot 放在了其最终位置 L(k) 上，这个过程称为一趟快速排序（或一次划分）。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 快速排序
void QuickSort(int A[], int low, int high) {
    if (low < high) {  //递归跳出的条件
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);   // 划分左子表
        QuickSort(A, pivotpos + 1, high);  // 划分右子表
    }
}

// 用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[], int low, int high) {
    int pivot = A[low];  // 第一个元素作为枢轴
    while (low < high) {
        while (low < high && A[high] > pivot) {
            --high;
        }
        A[low] = A[high];  // 比枢轴小的元素移动到左端
        while (low < high && A[low] <= pivot) {
            ++low;
        }
        A[high] = A[low];  // 比枢轴大的元素移动到右端
    }
    A[low] = pivot;  // 枢轴元素存放到的最终位置
    return low;
}

快速排序算法的性能分析如下：

空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。 最好情况下为 $O(\log_{2}{n})$ ；最坏情况下，因为要进行 $n-1$ 次递归调用，所以栈的深度为 $O(n)$ ；平均情况下，栈的深度为 $O(\log_{2}{n})$。

时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含 $n-1$ 个元素和 0 个元素时，这种最大程度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 $O(n^2)$。

有很多方法可以提高算法的效率：一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即 Partition() 可能做到最平衡的划分，得到的两个子问题的大小都不可能大于 $\frac{n}{2}$ ，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 $O(n\log_{2}{n})$ 。 好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。

注意：在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准）元素放到其最终的位置上。

选择排序

选择排序的基本思想是：每一趟（如第 $i$ 趟）在后面 $n-i+1 \ (i=1,2,\cdots ,n-1)$ 个待排序元素中选取关键字最小的元素，作为有序子序列的第 $i$ 个元素，直到第 $n-1$ 趟做完，待排序元素只剩下 1 个，就不用再选了。

简单选择排序

根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想：假设排序表为 $L[1…n]$ ，第 $i$ 趟排序即从 $L[i…n]$ 中选择关键字最小的元素与 $L(i)$ 交换，每一趟排序可以确定一个元素的最终位置，这样经过 $n-1$ 趟排序就可使得整个排序表有序。简单选择排序算法的代码如下：

1
2
3
4
5
6
7
8
void SelectSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) {    // 一共进行n-1趟
        int min = i;                     // 记录最小元素位置
        for (int j = i + 1; j < n; j++)  // 在A[i...n-1]中选择最小的元素
            if (A[j] < A[min]) min = j;  // 更新最小元素位置
        if (min != i) swap(A[i], A[min]);  //封装的 swap() 函数共移动元素3次
    }
}

简单选择排序算法的性能分析如下：

空间效率：仅使用常数个辅助单元，故空间效率为 $O(1)$。

时间效率：从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过 $3(n- 1)$ 次，最好的情况是移动 0 次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是 $\frac{n(n- 1)}{2}$ 次，因此时间复杂度始终是 $O(n^2)$ 。

稳定性：在第 $i$ 趟找到最小元素后，和第 $i$ 个元素交换，可能会导致第 $i$ 个元素与其含有相同关键字元素的相对位置发生改变。因此，简单选择排序是一种不稳定的排序方法。

堆排序

堆的定义如下，$n$ 个关键字序列 L[1..n] 称为堆，当且仅当该序列满足：

  1. L(i)>=L(2i) 且 L(i)>=L(2i+1) 或
  2. L(i)<=L(2i) 且 L(i)<=L(2i+1) （$1\le i \le \left \lfloor \frac{n}{2} \right \rfloor $）

可以将该一维数组视为一棵完全二叉树，

  • 满足条件 1 的堆称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。
  • 满足条件 2 的堆称为小根堆（小顶堆），小根堆的定义刚好相反，根结点是最小元素。

堆排序的思路很简单：首先将存放在 L[1...n] 中的 $n$ 个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决两个问题：

  1. 如何将无序序列构造成初始堆
  2. 输出堆顶元素后，如何将剩余元素调整成新的堆

堆排序的关键是构造初始堆。$n$ 个结点的完全二叉树，最后一个结点是第 $\left \lfloor \frac{n}{2} \right \rfloor$ 个结点的孩子。对第 $\left \lfloor \frac{n}{2} \right \rfloor$ 个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对各结点（ $\left \lfloor \frac{n}{2} \right \rfloor -1 \sim 1$） 为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。

下面是建立大根堆算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 建立大根堆
void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i > 0; i--) {  // 从后往前调整所有的非终端结点
        HeadAdjust(A, i, len);
    }
}

// 将以 k 为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k];                             // A[0] 暂存子树的根节点
    for (int i = 2 * k; i <= len; i *= 2) {  // 沿 key 较大的子结点向下筛选
        if (i < len && A[i] < A[i + 1]) { // i < len 保证有右兄弟
            i++;  // 取 key 较大的子结点的下标
        }
        if (A[0] >= A[i]) {
            break;  // 筛选结束
        } else {
            A[k] = A[i];  // 将 A[i] 调整到双亲结点上
            k = i;        // 修改 k 值，以便继续向下筛选
        }
    }
    A[k] = A[0];  // 被筛选结点的值放入最终位置
}

下面是堆排序算法：

1
2
3
4
5
6
7
void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);  // 初始建堆
    for (int i = len; i > 1; i--) {
        Swap(A[i], A[1]);  // 输出堆顶元素（和堆底元素交换）
        HeadAdjust(A, 1, i - 1);  // 调整，把剩余的 i-1 个元素整理成堆
    }
}

堆排序适合关键字较多的情况（如 $n>1000$ ）。例如，在 1 亿个数中选出前 100 个最大值。首先使用一个大小为 100 的数组，读入前 100 个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。

堆排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，所以空间复杂度为 $O(1)$。

时间效率：建堆时间为 $O(n)$ 【推导过程】，之后有 $n- 1$ 次向下调整操作，每次调整的时间复杂度为 $O(h)$，故在最好、最坏和平均情况下，堆排序的时间复杂度为 $O(n \log_{2}{n})$。

稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。

堆的插入：新元素放到表尾（堆底），根据大/小根堆的要求，新元素不断“上升”，直到无法继续上升为止。每次“上升”调整只需对比关键字 1 次。

堆的删除：被删除元素用表尾（堆底）元素代替，根据大/小根堆的要求，替代元素不断“下坠”，知道无法继续下坠为止。每次“下坠”调整可能需要对比关键字 2 次，也可能只需对比 1 次。

归并排序和基数排序

归并排序

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

$m$ 路归并，每选出一个元素需要对比关键字 $m-1$ 次

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdlib>
int n = A.length;
int *B = (int *)malloc(n * sizeof(int));  // 辅助数组B
// A[low..mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) {
        B[k] = A[k];  // 将 A 中所有元素复制到 B 中
    }
    for (i = low, j = mid + 1, k = i; i < mid && j <= high; k++) {
        if (B[i] <= B[j]) {
            A[k] = B[i++];  // 将较小值复制到 A 中
        } else {
            A[k] = B[j++];
        }
    }
    while (i <= mid) {  // 处理剩余大值元素
        A[k++] = B[i++];
    }
    while (j <= high) {
        A[k++] = B[j++];
    }
}

注意：上面的代码中，最后两个 while 循环只有一个会执行。

一趟归并排序的操作是，调用 $\left \lceil \frac{n}{2h} \right \rceil $ 次算法 merge()，将 L[1...n] 中前后相邻且长度为 $h$ 的有序段进行两两归并，得到前后相邻、长度为 $2h$ 的有序段，整个归并排序需要进行 $\left \lceil \log_{2}{n} \right \rceil $ 趟。

递归形式的 2 路归并排序算法是基于分治的，其过程如下。

分解：将含有 $n$ 个元素的待排序表分成各含 $\frac{n}{2}$ 个元素的子表，采用 2 路归并排序算法对两个子表递归地进行排序。

合并：合并两个已排序的子表得到排序结果。

1
2
3
4
5
6
7
8
void MergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;   // 从中间划分
        MergeSort(A, low, mid);       // 对左半部分归并排序
        MergeSort(A, mid + 1, high);  // 对右半部分归并排序
        Merge(A, low, mid, high);     // 归并
    }
}

2 路归并排序算法的性能分析如下：

空间效率：Merge() 操作中，辅助空间刚好为 $n$ 个单元，所以算法的空间复杂度为 $O(n)$ 。

时间效率：每趟归并的时间复杂度为 $O(n)$，共需进行 $\left \lceil \log_{2}{n} \right \rceil $ 趟归并，所以算法的时间复杂度为 $O(n \log_{2}{n})$。

稳定性：由于 Merge() 操作不会改变相同关键字记录的相对次序，所以 2 路归并排序算法是一种稳定的排序方法。

注意：一般而言，对于 $N$ 个元素进行 $k$ 路归并排序时，排序的趟数 $m$ 满足 $K^m=N$，从而 $m=\log_{k}{N}$，又考虑到 $m$ 为整数，所以 $m=\left \lceil \log_{k}{N} \right \rceil$ 。这和前面的 2 路归并是一致的。

基数排序

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

假设长度为 $n$ 的线性表中每个结点 $a_j$ 的关键字由 $d$ 元组（$k_{j}^{d-1} , k_{j}^{d-2} , \cdots , k_{j}^{1} , k_{j}^{0}$）组成，满足 $0 \le k_{j}^{i} \le r-1 \ (0\le j <n , 0 \le i \le d-1) $。其中 $k_{j}^{d-1}$ 为主位关键字，$k_{j}^{0}$ 为最次位关键字。

为实现多关键字排序，通常有两种方法：

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

下面描述以 $r$ 为基数的最低位优先基数排序的过程，在排序过程中，使用 $r$ 个队列 $Q_0 , Q_1 , \cdots ,Q_{r-1}$ 。基数排序的过程如下：对 $i=0 , 1 , \cdots , d-1$ ，依次做一次 “分配”和“收集”（其实是一次稳定的排序过程）。

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

基数排序算法的性能分析如下：

空间效率：趟排序需要的辅助存储空间为 $r$ （ $r$ 个队列：$r$ 个队头指针和r个队尾指针），但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为 $O®$。

时间效率：基数排序需要进行 $d$ 趟分配和收集，一趟分配需要 $O(n)$，一趟收集需要 $O®$ ，所以基数排序的时间复杂度为 $O(d(n+ r))$ ，它与序列的初始状态无关。

稳定性：对于基数排序算法而言，很重要一点就是按位排序时必须是稳定的。因此，这也保证了基数排序的稳定性。

基数排序擅长解决的问题：

  1. 数据元素的关键字可以方便地拆分为 $d$ 组，且 $d$ 较小
  2. 每组关键字的取值范围不大，即 $r$ 较小
  3. 数据元素个数 $n$ 较大

外部排序

外部排序的基本概念

在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。这种排序方法就称为外部排序。

外部排序的方法

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读/写的机械动作所需的时间远远超过内存运算的时间（相比而言可以忽略不计），因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即 I/O 次数。
外部排序通常采用归并排序法。它包括两个相对独立的阶段：

  1. 根据内存缓冲区大小，将外存上的文件分成若干长度为 $l$ 的子文件，依次读入内存并利用内部排序方法对它们进行排序，
    并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串
  2. 对这些归并段进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。

一般地，对 $r$ 个初始归并段，做 $k$ 路平衡归并：

  1. 最多只能有 $k$ 个段归并为一个；
  2. 每一趟归并中，若有 $m$ 个归并段参与归并，则经过这一趟处理得到 $\left \lceil \frac{m}{k} \right \rceil $ 个新的归并段。

第一趟可将 $r$ 个初始归并段归并为 $\left \lceil \frac{r}{k} \right \rceil $ 个归并段，以后每趟归并将 $m$ 个归并段归并成 $\left \lceil \frac{m}{k} \right \rceil $ 个归并段，直至最后形成一个大的归并段为止。树的高度 $=\left \lceil \log_{k}{r} \right \rceil = $ 归并趟数 $S$ 。可见，只要增大归并路数 $k$ ，或减少初始归并段个数 $r$ ，都能减少归并趟数 $S$，进而减少读写磁盘的次数，达到提高外部排序速度的目的。

多路归并带来的负面影响：

  1. $k$ 路归并时，需要开辟 $k$ 个输入缓冲区，内存开销增加
  2. 每挑选一个关键字需要对比关键字 $k-1$ 次，内部归并所需时间增加

多路平衡归并与败者树

增加归并路数 $k$ 能减少归并趟数 $S$，进而减少 I/O 次数。然而，增加归并路数 $k$ 时，内部归并的时间将增加。做内部归并时，在 $k$ 个元素中选择关键字最小的记录需要比较 $k-1$ 次。每趟归并 $n$ 个元素需要做 $(n- 1)(k- 1)$ 次比较，$S$ 趟归并总共需要的比较次数为 $$S(n-1)(k-1)=\left \lceil \log_{k}{r} \right \rceil (n-1)(k-1)=\frac{\left \lceil \log_{2}{r} \right \rceil(n-1)(k-1)}{\left \lceil \log_{2}{k} \right \rceil}$$式中，$\frac{k-1}{\left \lceil \log_{2}{k} \right \rceil}$ 随 $k$ 增长而增长，因此内部归并时间亦随 $k$ 的增长而增长。这将抵消由于增大 $k$ 而减少外存访问次数所得到的效益。因此，不能使用普通的内部归并算法。

为了使内部归并不受 $k$ 的增大的影响，引入了败者树。败者树是树形选择排序的一种变体，可视为一棵完全二叉树。$k$ 个叶结点分别存放 $k$ 个归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

因为 $k$ 路归并的败者树深度为 $\left \lceil \log_{2}{k} \right \rceil$， 因此 $k$ 个记录中选择最小关键字，最多需要 $\left \lceil \log_{2}{k} \right \rceil$ 次比较。所以总的比较次数为：$$S(n-1)\left \lceil \log_{2}{k} \right \rceil=\left \lceil \log_{k}{r} \right \rceil (n-1)\left \lceil \log_{2}{k} \right \rceil =(n-1)\left \lceil \log_{2}{r} \right \rceil$$可见，使用败者树后，内部归并的比较次数与 $k$ 无关了。因此，只要内存空间允许，增大归并路数 $k$ 将有效地减少归并树的高度，从而减少 I/O 次数，提高外部排序的速度。

值得说明的是，归并路数 $k$ 并不是越大越好。归并路数 $k$ 增大时，相应地需要增加输入缓冲区的个数。若可供使用的内存空间不变，势必要减少每个输入缓冲区的容量，使得内存、外存交换数据的次数增大。当 $k$ 值过大时，虽然归并趟数会减少，但读写外存的次数仍会增加。

置换－选择排序（生成初始归并段）

减少初始归并段个数 $r$ 也可以减少归并趟数 $S$ 。若总的记录个数为 $n$ ，每个归并段的长度为 $l$ ，则归并段的个数 $r=\left \lceil \frac{n}{l} \right \rceil $。采用内部排序方法得到的各个初始归并段长度都相同（除最后一段外），它依赖于内部排序时可用内存工作区的大小。因此，必须探索新的方法，用来产生更长的初始归并段。

设初始待排文件为 FI，初始归并段输出文件为 FO，内存工作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 $w$ 个记录。置换-选择算法的步骤如下:

  1. 从 FI 输入 $w$ 个记录到工作区 WA。
  2. 从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录。
  3. 将 MINIMAX 记录输出到 FO 中去。
  4. 若 FI 不空，则从 FI 输入下一个记录到 WA 中。
  5. 从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录。
  6. 重复 3~5，直至在 WA 中选不出新的 MINIMAX 记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到 FO 中去。
  7. 重复 2~6，直至 WA 为空。由此得到全部初始归并段。

上述算法，在 WA 选择 MINIMAX 记录的过程需利用败者树来实现

最佳归并树

归并过程中的磁盘 I/O 次数 = 归并树的 WPL * 2

要让磁盘 I/O 次数最少，就要使归并树 WPL 最小，即哈夫曼树

将哈夫曼树的思想推广到 $m$ 叉树的情形，在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的 I/O 次数最少的最佳归并树。

若初始归并段不足以构成一棵严格 $k$ 叉树时，需添加长度为 0 的“虚段”，按照哈夫曼树的原则，权为 0 的叶子应离树根最远。

如何判定添加虚段的数目

设度为 0 的结点有 $n_0 (=n)$ 个，度为 $k$ 的结点有 $n_k$ 个，则对严格 $k$ 叉树有 $n_0=(k-1)n_k+1$，由此可得 $n_k=\frac{(n_0-1)}{(k-1)}$。

  • 若 $(n_0-1) \bmod (k-1)=0 $ ，则说明这 $n_0$ 个叶结点（初始归并段）正好可以构造 $k$ 叉归并树。此时，内结点有 $n_k$ 个。
  • 若 $(n_0-1) \bmod (k-1) =u \ne 0$ ，则说明对于这 $n_0$ 个叶结点，其中有 $u$ 个多余，不能包含在 $k$ 叉归并树中。为构造包含所有 $n_0$ 个初始归并段的 $k$ 叉归并树，应在原有 $n_k$ 个内结点的基础上再增加 1 个内结点，即再加上 $k-u-1$ 个空归并段，就可以建立归并树。