第七章排序

数据结构目录阅读速览下载 Markdown

一、排序概念

为什么要排序

查找表明，有序表的查找可远远快于无序表。如有序表的二分查找就能使时间复杂度降到 $O(\log_2 n)$ ，因此排序是常见的数据操作之一。

关键字（排序依据）

通常待处理的数据不是单一的值，而是含有若干个字段的复杂数据记录，选择其一字段的值作为排序中比较的依据，该字段称作关键字。排序只涉及到关键字，下文中数据值特指该数据的关键字值。

排序的稳定性

待排序数据中如果有关键字值相同的元素，经过某种排序算法后其相对先后位置在排序前后没有变化，这种排序称稳定排序，使用的算法称稳定排序算法。反之，如果不能保证其相对先后位置保持不变，称不稳定排序，算法称不稳定排序算法。

设数据 $R_i$ 和 $R_j$ 关键字值相同，且排序前 $R_i$ 在 $R_j$ 之前。稳定排序后一定保持 $R_i$ 在 $R_j$ 之前；不稳定排序后，有可能变为 $R_i$ 在 $R_j$ 之后。

内排序与外排序

待排序数据可全部一次性载入内存，排序只和内存打交道，在程序中的具体表现就是数据可以全部放入声明的一组变量中，该排序操作称为内排序。

如果待排序数据不能一次性全部载入内存，在排序过程中还需要进行内、外存之间的数据交换，在程序中的具体表现是数据只能分批从文件中读入内存变量中，该排序称为外部排序。

排序的基础操作与默认约定

排序算法中，比较和交换是基础。编程语言提供的比较操作是一个二元操作，它给出了 >、>=、<、<=、== 五种关系的比较操作，所有的比较操作均以此为基础；如何反复利用二元操作中的两两比较完成排序任务是以下所有算法的主线。

如无特殊说明，排序后都假定是非递减的序列。

算法 + 数据结构 = 程序。

二、内排序

2.1 冒泡排序（Bubble Sort）

核心思想

冒泡排序以两两比较为基础。

第一趟排序的过程：第 1 和第 2 个元素比较，如果第 1 个元素大于第 2 个元素，两者交换；第 2 和第 3 个元素比较，如果第 2 个元素大于第 3 个元素，两者交换；如此操作，直到第 $n-1$ 个元素和第 $n$ 个元素比较、交换后，最大元素被换到了序列尾部即第 $n$ 个位置上，此称第一趟排序。

之后，在前 $n-1$ 个元素中进行如上操作，次大元素被换到了第 $n-1$ 的位置上，此称第二趟排序。

依此方法操作，直到前面余下的元素个数为 1 时停止，结果是无序序列变为有序序列。

过程示例（数值演示的一般规律）

以待排序序列 18, 26, 31, 72(a), 8, 15, 88, 72(b), 35, 20 为例（72(a)、72(b) 为两个相等元素的标记，用于观察稳定性）。每一趟将当前未排定部分中的最大元素"冒泡"到序列末端并排定（幻灯片中以下划线标出已排定的尾部）：第一趟排定 88，序列为 18, 26, 31, 8, 15, 72(a), 72(b), 35, 20, 88；第二趟排定 72(b)，序列为 18, 26, 8, 15, 31, 72(a), 35, 20, 72(b), 88；第三趟排定 72(a)，序列为 18, 8, 15, 26, 31, 35, 20, 72(a), 72(b), 88；……至第九趟序列变为有序：8, 15, 18, 20, 26, 31, 35, 72(a), 72(b), 88。

C++ 代码实现

原型法：先实现第一趟排序。提示：顺序结构实现后，注意检查循环的左右边界，以免数组访问越界——左边界 $i=0$ ，a[0] 和 a[1] 比；右边界 $i=n-2$ ，a[n-2] 和 a[n-1] 比。

代码

for (i=0; i<n-1; i++)
    if (a[i]>a[i+1]){
        tmp = a[i];
        a[i] = a[i+1];
        a[i+1] = tmp;
    }

泛化：在外循环中用 $j$ 逐渐递减内循环 $i$ 的右边界，从 $n-2$ 、 $n-3$ 、… 逐步递减到 1。外循环 $j$ 的左边界为 $j=n-1$ （此时内循环如上页原型），右边界为 $j=1$ （此时内循环仅 a[0] 和 a[1] 比）。

代码

for (j=n-1; j>0; j--)
    for (i=0; i<j; i++)
        if (a[i]>a[i+1])
        {
            tmp = a[i];
            a[i] = a[i+1];
            a[i+1] = tmp;
        }

优化

当某趟排序中一次交换都没有发生，说明已经有序；因此可每趟排序设置是否发生交换的标志。

代码

template <class elemType>
void bubbleSort(elemType a[], int n)
{
    int i, j;
    bool change = true;
    elemType tmp;
    for (j=n-1; j>0 && change; j--)
    {
        change = false;
        for (i=0; i<j; i++)
            if (a[i]>a[i+1])
            {
                tmp = a[i];
                a[i] = a[i+1];
                a[i+1] = tmp;
                change = true;
            }
    }
}

外循环条件为 j>0 && change：每趟开始前将 change 置为 false，发生交换时置为 true；若整趟无交换则 change 仍为 false，外循环提前结束。

稳定性

冒泡排序是稳定排序。原因：在两两比较时，前者和后者相邻，且前者大于后者才交换，相等则保持不动。

从上图示例中，可看出 72(a)、72(b) 在排序前后相对位置不变。

复杂度分析

内外循环相互不独立，打开外循环：当 $j=n-1$ 时比较 $n-1$ 次；当 $j=n-2$ 时比较 $n-2$ 次；……当 $j=1$ 时比较 1 次。共 $(1+2+3+\dots+n-1)=n(n-1)/2$ 次。

最差时，每趟都有交换，复杂度 $O(n^2)$ 。

最好时，第一趟就没有交换（原本有序），复杂度 $O(n)$ 。

总体介于两者之间，一般称其复杂度为 $O(n^2)$ 。

易错点

顺序结构实现后，注意检查循环的左右边界，以免数组访问越界：内层比较 a[i] 与 a[i+1]，左边界 $i=0$ ，右边界 $i=n-2$ ；外循环 $j$ 从 $n-1$ 递减到 1。

2.2 插入排序（Insertion Sort）

核心思想

以两两比较为基础，将一个元素插入到有序序列中的适当位置。

将无序序列排成有序序列的整体策略：首先将序列中仅由第 1 个元素构成的序列视作一个有序序列；再将第 2 个元素插入到前面有 1 个元素的有序序列中，形成有 2 个元素的有序序列。

再将第 3 个元素插入到前面有 2 个元素的有序序列中，形成有 3 个元素的有序序列。

如此操作，直到将第 $n$ 个元素插入到前面有 $n-1$ 个元素的有序序列中，最终形成有 $n$ 个元素的有序序列。

单次插入的过程要点

以"将 15 插入有序序列 8, 18, 26, 31, 72(a)"为例：从有序序列尾部开始，凡是比待插元素大的元素依次向后移动一位（腾出空位/洞），洞随之不断向前移动；当遇到第一个不比待插元素大的元素时停止，把待插元素存入腾出的空位。最终序列变为 8, 15, 18, 26, 31, 72(a)，即 15 被放到 8 与 18 之间。

单元素插入的 C++ 代码

代码

template <class elemType>
void insert(elemType a[], int n, const elemType &x)
//n 为有序表 a 中当前元素的个数，x 为待插入新元素
{
    int i;
    // 从后往前找第一个不比 x 大的元素，大者后移一位
    for (i=n-1; i>=0; i--)
        if (a[i]<=x) break;
        else a[i+1] = a[i];
    a[i+1] = x; // 在腾出的位置上存新元素 x
}

关键点：循环从下标 n-1 向 0 递减扫描；遇到 a[i]<=x 时 break（找到插入位置），否则将 a[i] 后移到 a[i+1]；循环结束后统一在 a[i+1] 处写入 x。

整体插入排序的 C++ 代码

代码

template <class elemType>
void insertSort(elemType a[], int n)
{
    int i;
    elemType tmp;

    // 将第 i 个元素插入到前 i-1 个元素的有序序列中
    for (i=1; i<n; i++)
    {
        tmp = a[i];
        insert(a, i, tmp);
    }
}

外层循环从 i=1 开始（第 0 个元素自成有序序列），每趟取出 a[i] 暂存到 tmp，再调用 insert(a, i, tmp) 将其插入到前 i 个元素构成的有序序列中。

排序过程的关键观察

以待排序序列 18, 26, 31, 72(a), 8, 15, 88, 72(b), 35, 20 为例：前三趟新元素本就大于前面有序段的所有元素（依次插入 26、31、72(a)），序列保持不变，仅做比较而不发生移动；第四趟遇到较小元素 8 时，它被插入到有序段的最前端，引发多个元素后移得到 8, 18, 26, 31, 72(a), 15, 88, 72(b), 35, 20；第五趟插入 15 得到 8, 15, 18, 26, 31, 72(a), 88, 72(b), 35, 20。每一趟使有序段长度加一，第九趟后整个序列有序，结果为 8, 15, 18, 20, 26, 31, 35, 72(a), 72(b), 88。

复杂度分析

当待排序序列原本正序时：每次插入一个元素只需比较一次，数据无需移动，此时算法的时间复杂度为 $O(n)$ ，为最优情况。

当待排序序列原本逆序时：每次插入一个元素都需要比较前面所有元素，数据全部需要移动，此时比较次数和移动次数都为 $\dfrac{n(n-1)}{2}$ ，算法的时间复杂度达到 $O(n^2)$ ，为最差情况。

一般称其复杂度为 $O(n^2)$ 。

稳定性

插入位置上及之后所有元素都大于 $x$ ，原本在 $x$ 前又和 $x$ 值相等的元素依然保留在 $x$ 插入位置之前，故为稳定排序。

2.3 希尔排序（Shell Sort）

核心思想

希尔排序的思想：先做预处理使序列比较有序，然后再进行插入排序。

预处理方法：将原始序列按不同步长（step）分成若干子序列，分别进行插入排序，使序列变比较有序，降低插入排序时间消耗。

子序列划分与过程要点

按步长 step 分组时，下标间隔为 step 的元素归入同一子序列；step 不同则划分出的子序列不同。

step 的取值一般从 $n/2$ 开始，之后逐次减半直到 1；按整数除法取步长时，step 的个数约为 $\lfloor\log_2 n\rfloor$ （当 $n$ 为 2 的幂时为 $\log_2 n$ ）。

每一个 step 值做一趟预处理（对各子序列做插入排序），最后一趟 step=1 即为对整个序列做一次简单插入排序，得到最终有序结果。

以待排序序列 18, 26, 31, 72(a), 8, 15, 88, 72(b), 35, 20（共 10 个元素）为例，演示三趟处理。

第一趟 step=5：划分出的子序列及其插入排序结果为——子序列1 18,15→15,18；子序列2 26,88→26,88；子序列3 31,72(b)→31,72(b)；子序列4 72(a),35→35,72(a)；子序列5 8,20→8,20。经 step=5 的子序列排序后形成的序列为 15, 26, 31, 35, 8, 18, 88, 72(b), 72(a), 20。

第二趟 step=2：以序列 15, 26, 31, 35, 8, 18, 88, 72(b), 72(a), 20 为输入，划分出的子序列及其插入排序结果为——子序列1 15,31,8,88,72(a)→8,15,31,72(a),88；子序列2 26,35,18,72(b),20→18,20,26,35,72(b)。经 step=2 的子序列排序后形成的预处理结果为 8, 18, 15, 20, 31, 26, 72(a), 35, 88, 72(b)。

第三趟 step=1：对序列 8, 18, 15, 20, 31, 26, 72(a), 35, 88, 72(b) 做简单插入排序，处理后结果为 8, 15, 18, 20, 26, 31, 35, 72(a), 72(b), 88。

C++代码

代码

template <class elemType>
void shellSort(elemType a[], int n)
{
    int step, i, j;
    elemType tmp;
    for (step = n / 2; step > 0; step /= 2)
        for (i = step; i < n; i++)
        {
            tmp = a[i];
            j = i;
            while ((j - step >= 0) && (tmp <= a[j - step]))
            {
                a[j] = a[j - step];
                j -= step;
            }
            a[j] = tmp;
        }
}

外层循环控制步长 step 从 $n/2$ 起，每次 step /= 2，直到 step > 0 不成立；中层循环 i 从 step 开始遍历到 n-1，对各子序列做带步长的插入排序；内层 while 用 tmp 暂存待插入元素 a[i]，沿步长方向回探并后移元素。

内层 while 的判定为 (j - step >= 0) && (tmp <= a[j - step])，其中 j - step >= 0 用于防止下标越界，tmp <= a[j - step] 决定是否继续后移；移动时执行 a[j] = a[j - step]; j -= step;，循环结束后将 tmp 放入 a[j]。

参考演示：https://algorithm-visualizer.org/brute-force/shellsort

复杂度分析

希尔排序预处理时间分析较复杂，这个不做进一步分析。

算法含三重循环；外、中两重循环就已经达到了 $n \log_2 n$ 。

稳定性

希尔排序是不稳定排序。原因：值相等的元素在预处理时可能分在不同的子序列中，经过在各自子序列中位置的调整，原本的相对前后位置就可能发生改变。

反例（待排序序列 80, 30(a), 30(b), 50）：step=2 时的预处理结果为 30(b), 30(a), 80, 50，step=1 时的简单插入排序结果为 30(b), 30(a), 50, 80；可见 30(a) 与 30(b) 的相对次序被颠倒。

2.4 归并排序（Merge Sort）

核心思想

归并排序基于"将两个有序序列归并为一个有序序列"的方法。

把原始序列中每个元素都看作一个长度为 1 的有序序列，经过两两归并，形成多个长度为 2 的有序序列；再经过相邻两个有序序列归并，形成多个长度为 4 的有序序列；反复如此，最后形成一个长度为 $n$ 的有序序列。

两路归并（merge）的过程要点

设两个有序序列分别用下标 $i$ 、 $j$ 扫描，结果序列用下标 $k$ ，初始 $i=0$ 、 $j=0$ 、 $k=0$ 。每一步：经过 $a[i]$ 、 $b[j]$ 比较后， $c[k]$ 取较小者；若取自 $a$ （取 $a[i]$ ）则 $i=i+1$ 、 $k=k+1$ 、 $j$ 不变，若取自 $b$ （取 $b[j]$ ）则 $j=j+1$ 、 $k=k+1$ 、 $i$ 不变。

当一方下标越界时，结束逐个比较，把另一序列中所有剩余元素直接抄入结果序列 $c$ ；两个下标都越界时结束合并。

以 $a=8,15,31$ 与 $b=18,20,26,35,72$ 归并为例：较小元素先进入结果序列，扫描指针只在被取走元素的那一侧前移；当较短序列 $a$ 先扫描完（ $i$ 越界）时，把较长序列 $b$ 中尚未取走的剩余元素（此处为 $72$ ）按原顺序抄入结果，最终合并结果为 $8,15,18,20,26,31,35,72$ 。

在数组中归并的存储约定

将两个有序序列均放在同一个数组 $a$ 中：下标从 low 到 mid 存储第一个有序序列，下标从 mid+1 到 high 存储第二个有序序列。

C++代码：merge

代码

template <class elemType>
void merge(elemType a[], int low, int mid, int high)
{
    int i, j, k;
    elemType *c;
    // 创建实际空间存储合并后结果
    c = new elemType[high - low + 1];
    i = low;
    j = mid + 1;
    k = 0;
    // 两个有序序列中元素的比较合并
    while ((i <= mid) && (j <= high)){
        if (a[i] <= a[j]){
            c[k] = a[i];
            i = i + 1;
        }
        else{
            c[k] = a[j];
            j = j + 1;
        }
        k = k + 1;
    }
    // 若 a 序列中 i 未越界，抄写剩余元素
    while (i <= mid){
        c[k] = a[i];
        i = i + 1;
        k = k + 1;
    }
    // 若 b 序列中 j 未越界，抄写剩余元素
    while (j <= high){
        c[k] = a[j];
        j = j + 1;
        k = k + 1;
    }
    for (i = 0; i < high - low + 1; i++)
        a[i + low] = c[i];
    delete[] c;
}

代码边界要点：辅助数组大小为 high - low + 1；主循环条件 (i <= mid) && (j <= high)，任一序列扫描完即退出；取等时（a[i] <= a[j]）优先取前一序列的元素 a[i]；退出主循环后用两个 while 把未越界一侧剩余元素抄完；最后用 for (i = 0; i < high - low + 1; i++) a[i + low] = c[i]; 将结果回写到原数组对应区间，并 delete[] c; 释放空间。

C++代码：mergeSort（递归分治）

代码

template <class elemType>
void mergeSort(elemType a[], int n)
{
    mergeSort(a, 0, n - 1);
}

template <class elemType>
void mergeSort(elemType a[],
               int low, int high)
{
    int mid;
    if (low >= high) return;
    mid = (low + high) / 2;
    mergeSort(a, low, mid);
    mergeSort(a, mid + 1, high);
    merge(a, low, mid, high);
}

体会递归调用中分割和合并的过程：递归出口为 low >= high，先取中点 mid = (low + high) / 2，对 [low, mid] 与 [mid+1, high] 两半分别递归排序，再 merge 合并。

分割与合并示例

对序列 18,26,31,72(a),8,15,88,72(b),35,20 演示：左侧"分割"自顶向下按中点把序列不断二分（先分为 18,26,31,72(a),8 与 15,88,72(b),35,20，再继续二分），直到每段长度为 1；右侧"合并"自底向上把分割得到的相邻有序段两两归并，逐层合成，最终结果为 8、15、18、20、26、31、35、72(a)、72(b)、88。分割与合并在结构上对称。

示例中相同值的两个元素 72(a) 与 72(b) 在最终结果中仍保持 72(a) 在前、72(b) 在后的相对次序。

时间复杂度分析

直接从"两个有序序列中每个元素参与比较的次数"角度看，比较次数不确定，从这个角度分析较复杂。

换个角度，从结果序列观察：设两个序列长度分别为 $n$ 和 $m$ ，合并后长度为 $n+m$ ；归并的处理量为 $O(n+m)$ ，实际关键字比较次数在两个序列均非空时至多为 $n+m-1$ （一方越界后只需顺序抄入剩余元素）。

设原始序列长度为 $n$ 、消耗的时间函数为 $t(n)$ ，则有：

t(n)=t(n/2)+t(n/2)+2\cdot n/2

=2t(n/2)+n=2\big(t(n/4)+t(n/4)+2\cdot n/4\big)+n

=4t(n/4)+2n=4\big(t(n/8)+t(n/8)+2\cdot n/8\big)+2n

=8t(n/8)+3n=2^{3}t(n/2^{3})+3n

=\dots=2^{k}t(1)+kn

当 $n$ 按 2 的幂分析时， $k$ 为 $n$ 能被 2 除到 1 的次数，即 $\log_2 n$ ；一般 $n$ 取上界同阶，故时间复杂度为 $O(n\log_2 n)$ 。

稳定性

在两两合并算法中，对前后两个有序序列中元素比较时，后者元素大才能胜出，因此值相同的元素在合并中能保持原本的相对前后位置，归并排序是一个稳定排序。

值相同时取等比较 a[i] <= a[j] 让前一序列的元素先入结果，这正是稳定性得以保持的实现依据。

2.5 快速排序（Quick Sort）

核心思想

选择一个元素作为标杆（pivot），把所有小于它的元素移到它的前面、大于等于它的元素移到它的后面；对标杆前后两个子序列分别排序后，整个序列就有序了。

快速排序与其他排序在"每趟确定什么"上的区别：冒泡、插入每趟确定一个具体位置上的元素（一趟排序后该元素到位）；快速排序每趟"抠出"一个位置（确定标杆的最终位置）；希尔、归并每趟确定一个子序列的排序状态。

分割（partition）过程要点

以序列 18, 26, 31, 72(a), 8, 15, 88, 72(b), 35, 20 为例，揭示一趟分割的一般方法（采用"挖洞"思想）：

取首元素为标杆，temp = 18，首元素位置形成第一个"洞"，洞初始在最左侧。
洞在左时，从后往前（从右向左）逐个对比，找到第一个比 temp 小的值，将其移入洞中，洞随之移到右边（移到被取走值的位置）。
洞在右时，从前往后（从左向右）找到第一个比 temp 大的值，将其移入洞中，洞又移动到左边。
此后两侧搜索都"从刚才停下的位置继续"：右侧从上次位置继续向前搜第一个比 temp 小的元素，左侧从上次位置继续向后搜第一个比 temp 大的元素，交替进行、洞在左右之间来回移动。
当左、右两个搜索位置"聚头"（相遇）时，把 temp 中的标杆放到聚头的位置，本轮处理结束；本例标杆 18 最终落在第 3 个位置（聚头处），其左边元素都小于它、右边元素都大于等于它，得到 15, 8, 18, 72(a), 31, 26, 88, 72(b), 35, 20。
随后分别对 18 左边的子序列和右边的子序列进行同样的操作（递归）。

关键观察：分割并非靠相邻交换，而是靠"洞"在左右指针之间反复搬移元素，左右指针交替向中间逼近，相遇即标杆归位。

C++ 代码

驱动接口与递归框架（初始化标杆、洞和左右指针）：

代码

template <class elemType>
void quickSort(elemType a[], int n){
        quickSort(a, 0, n-1);
}
template <class elemType>
void quickSort(elemType a[], int start, int end){
        int i, j, hole;
        elemType temp;
        // 序列中没有元素或只有一个元素，递归结束
        if (end<=start) return;
        temp = a[start];
        hole = start;
        i=start; // 从左到右搜索的指针
        j=end;   // 从右到左搜索的指针

分割主循环与递归调用：

代码

        while (i<j){
                // 从 j 位置开始从后往前找第一个小于 temp 的值
                while ((j>i)&&(a[j]>=temp)) j--;
                if (j==i) break;
                a[hole]=a[j];
                hole = j;
                // 从 i 位置开始从前往后找第一个大于等于 temp 的值
                while ((i<j)&&(a[i]<temp)) i++;
                if (j==i) break;
                a[hole]=a[i];
                hole = i;
        }
        a[hole] = temp;
        // 对标杆位置左边的序列实施同样的方法
        quickSort(a,start, hole-1);
        // 对标杆位置右边的序列实施同样的方法
        quickSort(a,hole+1, end);
}

代码边界要点：递归出口为 if (end<=start) return;（区间元素个数 ≤1）；内层两个 while 都带 j>i / i<j 的越界与相遇保护，且每次 while 结束后用 if (j==i) break; 检测指针相遇以跳出循环；左右指针相遇后把 temp 写回 a[hole]，标杆位置即为 hole。

标杆常被称为 pivot。

时间复杂度分析

一趟（一次分割）的代价：无论标杆元素最后落在什么位置上，从左向右的搜索次数加上从右向左的搜索次数加起来都是 $n$ ，因此一趟的时间花费是 $O(n)$ 。

趟数取决于标杆落点：

最好情况：每趟都很幸运，标杆都落在中间位置，即把待处理元素分成长度最多相差 1 的两部分，这种情况趟数最少，为 $\log_2 n$ 趟，时间复杂度为 $O(n\log_2 n)$ 。
最坏情况：每次标杆落定后，其左边或者右边序列都有一个序列元素个数为 0，于是下趟序列仅比上趟少一个元素（如原本待处理数据为完全逆序或正序时），比较次数为 $n+(n-1)+\cdots+1$ ，时间复杂度为 $O(n^2)$ 。

稳定性

快速排序是不稳定排序。

原因：算法中标杆取最左侧元素，右边小于它的元素往左边的洞中移动，左边大于等于它的值往右边的洞中移动；当序列中有两个关键字值相同的元素且均小于标杆，其中一个居于序列最右侧时，第一次移动就把最右侧的那个相同元素移到了最左端，于是两个值相同元素的相对位置发生改变。

不稳定示例：对 80, 72(a), 72(b)，取 temp=80、hole=0；从右向左搜索把最右侧的 72(b) 移入洞（洞到 2），再把 72(a) 移入洞（洞到 1），最终结果为 72(b), 72(a), 80——两个相同关键字 72 的相对次序由 (a)、(b) 变为 (b)、(a)，相对位置发生变化。

易错点与实现约定

无论标杆取的是哪个位置上的元素，在排序前都需先把该标杆元素换到首位置上，以保证第一个洞一定在最左侧；这样才能先从右向左搜索。
也可以把首洞位置定在最右侧，此时前面的处理就要先从左向右搜索，而不是先从右向左搜索。即首洞位置与首次搜索方向必须配套。

优化方法

减小落到最坏情况概率的几种改进办法：

取中间位置的值作为标杆。
在首、尾、中间三个位置的值中找到中间值，将其作为标杆。

2.6 选择排序（Selection Sort）

核心思想

选择排序的思想以两两比较为基础。从左到右，为有序序列中每个位置选择合适的元素。具体为：在下标 $0\sim n-1$ 范围找出最小值，换到 $0$ 下标位置；在下标 $1\sim n-1$ 范围找出最小值，换到 $1$ 下标位置；……；在下标 $n-2\sim n-1$ 范围找出最小值，换到 $n-2$ 下标位置。每一趟在剩余未排序区间内确定一个目标位置应放的元素，已确定的前缀位置不再变动。

过程要点（数值演示的一般规律）

以序列 $18,26,31,72(a),8,15,88,72(b),35,20$ 为例，演示揭示的规律：

第 $k$ 趟（step $k$ ）为第 $k$ 个位置找到合适的元素，并换到第 $k$ 个位置上去。
step 1：在整个序列中最小值为 $8$ ，将其换到第 1 个位置；交换使原首位的 $18$ 被换到 $8$ 原来的位置上（即交换发生在两个位置之间）。
随着趟数推进，前缀逐位变为有序：step 2 确定第 2 位为 $15$ ，step 3 确定第 3 位为 $18$ ，依此类推；至 step 9 通过交换 $88$ 与 $72(a)$ ，最终局部次序为 $72(b),72(a),88$ ，体现相等关键字可能换序。
关键观察：每趟在区间内选出最小值后，被选中的最小值与当前目标位置上的元素互换；这一交换可能跨越多个不相邻元素。

C++ 代码

代码

template <class elemType>
void selectSort(elemType a[], int n)
{
    int i, j, minIndex; elemType temp;
    for (i = 0; i < n; i++)
    {
        // 为第 i 个位置找合适的数据
        minIndex = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[minIndex]) minIndex = j;
        // 将 minIndex 位置上的数据
        // 和位置 i 上数据交换
        if (minIndex == i) continue;
        temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

外层 for (i=0; i<n; i++) 逐个确定位置 $i$ 应放的元素；内层 for (j=i+1; j<n; j++) 在区间 $[i+1, n-1]$ 中扫描，用 minIndex 记录当前最小值的下标。
内层比较条件为 a[j] < a[minIndex]，命中时更新 minIndex = j。
边界处理：当 minIndex == i 时用 continue 跳过交换。
交换通过中间变量 temp 完成 a[i] 与 a[minIndex] 的互换。

复杂度分析

在 $[0,n-1]$ 中找最小值，比较 $n-1$ 次；在 $[1,n-1]$ 中找最小值，比较 $n-2$ 次；……；在 $[n-2,n-1]$ 中找最小值，比较 $1$ 次。共比较了

\frac{n(n-1)}{2}

次，时间复杂度为 $O(n^2)$ 。

稳定性

当找到最小值后，交换可能发生在不相邻元素之间，破坏了原本的顺序，故选择排序是不稳定排序。幻灯片给出的反例（含两个相等关键字 $72(a)$ 、 $72(b)$ ）：

Step 1（待排序序列）： $72(a), 72(b), 8$ 。
Step 2： $8, 72(b), 72(a)$ 。最小值 $8$ 被换到第 1 个位置，原首位的 $72(a)$ 被换到末位，于是 $72(b)$ 排到了 $72(a)$ 之前。
Step 3： $8, 72(b), 72(a)$ 。原本在前的 $72(a)$ 最终排在了 $72(b)$ 之后，相等元素的相对次序被颠倒。

易错点

内层循环起点是 j = i+1（从 $i$ 的下一个位置开始扫描），而非从 $0$ 或从 $i$ 开始。
内层扫描时维护的是最小值的下标 minIndex，整趟扫描结束后才进行一次交换，而非每比较一次就交换。
交换前需判断 minIndex == i，相等则 continue 跳过交换。
不稳定性来源于"跨不相邻位置的交换"，分析稳定性时应以相等关键字（如 $72(a)$ 、 $72(b)$ ）的相对次序是否改变为判据。

2.7 堆排序（Heap Sort）

堆的概念

大顶堆：一个完全二叉树中，任意一个结点的值不小于其左右子结点值。

小顶堆：一个完全二叉树中，任意一个结点的值不大于其左右子结点值。

大顶堆和小顶堆都称为堆。

核心思想

将存于数组中的序列看作是一棵完全二叉树的顺序存储。

按照堆的概念调整之，使之成为一个大顶堆。

摘取大顶，换到待处理元素最后位置。

继续调整新的根使之满足大顶堆概念，得到次大元素。

继续后移，直到序列中元素全部有序。

过程要点（建堆与摘取演示）

原始序列： $18,\ 26,\ 31,\ 72(a),\ 8,\ 15,\ 88,\ 72(b),\ 35,\ 20$ ，将其看作顺序存储的完全二叉树（根为 18，其左右子为 26、31；26 的左右子为 72(a)、8；31 的左右子为 15、88；72(a) 的左右子为 72(b)、35；8 的左子为 20）。

建堆方法：对序列从后往前逐一做元素检查、调整，使得以该元素为根的二叉树满足大顶堆的定义。

调整顺序（演示）：依次调整倒数第一个非叶子结点 8、倒数第二个非叶子结点 72(a)、倒数第三个非叶子结点 31、倒数第四个非叶子结点 26、倒数第五个非叶子结点 18，处理到根结点 18 调整完毕即获得大顶堆，堆顶为最大元素 88。

摘取（排序）方法：将大顶和当前序列最后一个元素交换，使最大元素获得最终定位；该元素不再参与调整，对新的根结点重新调整为大顶堆，从而得到次大元素并定位。如此循环（演示中先将 88 与最后一个元素交换、88 获得最终定位；88 不再参与调整，调整新的根结点 8，大顶和最后元素 8 交换，72(b) 获得最终定位）。

终止条件：如此继续操作，直到参与调整的个数为 1，便得到最后的状态，该状态在数组中就是一个有序序列。

演示最终结果：数组中元素为 $8,\ 15,\ 18,\ 20,\ 26,\ 31,\ 35,\ 72(a),\ 72(b),\ 88$ ，有序。

C++ 代码

主排序函数：先用从倒数第一个非叶子结点开始的循环首次建立大顶堆，再循环换大顶、逐次减少参与的元素并重新调整为大顶堆。

代码

template <class elemType>
void heapSort(elemType a[], int n){
    int i, j;
    elemType temp;
    // 从倒数第一个非叶子结点开始调整，
    // 首次建立大顶堆
    for (i=(n-1)/2; i>=0; i--) adjust(a, n, i);
    // 换大顶，逐次减少参与的元素，
    // 重新调整为大顶堆
    for (j=n-1; j>=1; j--){
        // 大顶和第 j 个位置元素交换
        temp = a[0]; a[0] = a[j]; a[j] = temp;
        // 调整第0个元素
        adjust(a, j, 0);
    }
}

下沉调整函数：对尺寸为 $n$ 的数组 $a$ ，假设根为 0 下标元素，调整下标为 $i$ 的元素，使得以 $i$ 为根的二叉树为一个大顶堆。

代码

template <class elemType>
void adjust(elemType a[], int n, int i){
    // 对尺寸为n的数组a，假设根为0下
    // 标元素，调整下标为i的元素，使
    // 得以i为根的二叉树为一个大顶堆。
    int maxChild;
    elemType temp;
    while (true){
        maxChild = 2 * i + 1; // i的左子下标
        if (maxChild > n - 1)
            return;
        if (maxChild + 1 <= n - 1) // i还有右子
            if (a[maxChild + 1] >= a[maxChild])
                maxChild++; // 右子最大
        if (a[i] > a[maxChild])
            return;
        temp = a[i];
        a[i] = a[maxChild];
        a[maxChild] = temp;
        i = maxChild; // 继续向下调整
    }
}

代码关键边界与要点：左子下标为 2 * i + 1，当 maxChild > n - 1 时无左子，直接 return（已是叶子）；只有 maxChild + 1 <= n - 1 时才存在右子，需要比较左右子取较大者（a[maxChild + 1] >= a[maxChild] 时令 maxChild++ 取右子）；若 a[i] > a[maxChild] 已满足大顶堆性质则 return；否则交换后令 i = maxChild 继续向下调整。

时间复杂度分析

堆排序时间消耗由两部分组成：初次建堆的时间消耗和摘取大顶的时间消耗。

前者从形式上看时间复杂度是 $O(n\log_2 n)$ ，但实际可达 $O(n)$ ；后者每次摘取后最多下沉 $O(\log_2 n)$ ，共进行 $n-1$ 次，故摘取阶段总时间为 $O(n\log_2 n)$ 。

建堆复杂度推导前提：假设堆的高度为 $h+1$ ，总的元素个数为 $n$ ；当堆是一个满二叉树时，有 $n = 2^{h+1} - 1$ 。

观察此堆，从后往前逐个检查并调整各个非叶子结点时，比较并调整的最大次数为以该结点为根的堆的高度 $-1$ 。

各层结点数与调整次数：第一批非叶子结点在倒数第二层，倒数第二层总的结点个数为 $2^{h-1}$ 个，各结点的比较调整最大次数为 1；倒数第三层总的结点个数为 $2^{h-2}$ 个，各结点的比较调整最大次数为 2；根结点这层的结点个数为 $2^{h-h}=2^0=1$ 个，结点比较调整最大次数为 $h$ 。

故总的比较调整次数最多为：

t=\sum_{i=h-1}^{0}2^{i}(h-i)=h+2(h-1)+4(h-2)+\cdots+2^{h-2}(2)+2^{h-1}(1)

2t=2h+4(h-1)+8(h-2)+\cdots+2^{h-1}(2)+2^{h}(1)

2t = 0 + 2h + 4(h-1) + 8(h-2) + \cdots + 2^{h-1}(2) + 2^{h}(1)

t = 2t - t = -h + 2 + 4 + 8 + \cdots + 2^{h-1} + 2^{h}

= -h - 1 + 1 + 2 + 4 + 8 + \cdots + 2^{h-1} + 2^{h}

= -(h+1) + \frac{1-2^{h+1}}{1-2} = -(h+1) + 2^{h+1} - 1 = n - (h+1)

又 $h$ 为 $n$ 的对数阶，故建堆的时间复杂度为 $O(n)$ 。

同样大顶和数组中最后一个元素交换后，堆的规模和高度也在逐渐变小，调整计算量的分析和建堆时间分析的一样，时间复杂度也为 $O(n\log n)$ 。

稳定性分析

在以上算法中可以看出，左、右子中选择最大元素时，右子是优先的：即如果左、右子一样大，选择右子为最大子，优先进入堆顶，并先于左子被替换到序列尾部；右子相对于左子，原本在数组序列中的位置就居于后面。

当父结点值和最大孩子结点的值相同时，该孩子也被换到上层，优先进入排序结果序列的尾部；这一局部情形不造成相等元素相对次序反转。

但当父结点值和最小结点的值相同时，情况可能发生反转，排序结果显示为不稳定排序。

稳定性反例：原始序列 $5(a),\ 80,\ 5(b)$ ，经堆排序后已排序序列为 $5(b),\ 5(a),\ 80$ ，相同值的两个 5 相对次序发生了反转。

对比示例：原始序列 $2,\ 5(a),\ 5(b)$ 与原始序列 $5(a),\ 2,\ 5(b)$ 经堆排序后均得到已排序序列 $2,\ 5(a),\ 5(b)$ （相同值的两个 5 次序保持）。

总结：堆排序算法是一个不稳定排序算法。

易错点

建堆调整必须从倒数第一个非叶子结点（下标 $(n-1)/2$ ）开始向前到根，而不是从根开始或从叶子开始。

调整 adjust 时参与范围由参数 $n$ （当前堆规模）控制，摘取阶段每趟把已定位的尾部元素排除在外（调用 adjust(a, j, 0)，规模逐次减小），已定位元素不再参与调整。

时间复杂度需区分建堆与摘取：建堆形式上可粗看为 $O(n\log_2 n)$ 、紧分析为 $O(n)$ ；摘取阶段为 $O(n\log_2 n)$ ，不能记成 $O(n)$ 。

判断稳定性时不能只看保持次序的样例，应注意父结点与较小孩子值相同导致的反转情形，故结论为不稳定。

2.8 优先队列（Priority Queue，堆的应用）

核心思想

优先队列出队时优先级高者先出队，而不是按入队先后顺序出队。

假设元素的值用其优先级的级别值来标识，级别值小的优先级高，反之则优先级低；出队时优先级高者（即级别值小者）先出队。

由于出队是优先级高者先出队，因此可以用一个小顶堆来实现优先级队列，堆顶是优先级最高的元素。

为什么用堆实现（与线性结构对比）

无论是顺序存储还是链式存储，进队、出队这两个操作总有一个时间复杂度是 $O(1)$ ，而另外一个是 $O(n)$ 。

改用小顶堆实现后，进队与出队的时间复杂度均可降到完全二叉树的高度 $O(\log_2 n)$ ，从而避免出现 $O(n)$ 的操作。

出队操作

出队取走优先级最高的元素，对应小顶堆的堆顶（即二叉树的根）。

操作步骤：

直接读取堆顶（即二叉树的根），时间花费为 $O(1)$ 。
摘取堆顶后，将尾部元素写入堆顶。
对 a[0] 做如上算法中的 adjust 调整操作，使其下沉到合适位置以恢复堆序，时间花费为此完全二叉树的高度 $O(\log_2 n)$ 。

因此出队的时间复杂度为 $O(\log_2 n)$ 。

出队示例（方法与关键观察）：对小顶堆执行一次出队时，先取走堆顶（如取走根 8），再把序列最后一个元素（如 88）移到根的位置；此时堆顶可能破坏堆序，对其执行向下调整——与较小的孩子比较并交换，逐层下沉，直到满足小顶堆性质为止。

进队操作

将新元素加入到序列尾部，成为完全二叉树最后的叶子结点。

由于该新叶子结点可能破坏了堆的有序性，因此需要向上检查其父结点，进行如下向上调整：

若新结点值不小于父结点，结束检查。
若新结点值小于父结点，则交换两者的值，并进一步往更高层祖先继续检查比较。
重复上述过程，直到新结点不小于其父结点，或者祖先结点已经到根为止。

因此进队的时间花费也是完全二叉树的高度 $O(\log_2 n)$ 。

进队示例（方法与关键观察）：

示例 1：新元素 10 进队，先插入到序列尾部成为最后的叶子结点（作为 31 的孩子）；与其父结点 31 比较，因 10 小于父结点 31 故交换两者的值；上升后 10 不小于其新父结点 8，于是结束调整。说明上浮在第一次遇到“新结点不小于父结点”时即停止。
示例 2：新元素 5 进队，插入尾部后一步步向上与父结点比较、交换，连续上浮多层，最终一直上浮到根的位置。说明当新元素优先级很高（值很小）时可能一路上浮成为新的堆顶。

复杂度小结

进队、出队均基于堆的向上 / 向下调整，时间复杂度都是完全二叉树的高度 $O(\log_2 n)$ ；其中出队读取堆顶本身仅 $O(1)$ ，瓶颈在调整步骤。

易错点

优先级约定方向：本课件规定级别值小者优先级高，故用小顶堆、堆顶为优先级最高元素；不要弄反成大顶堆。
出队时是“摘走堆顶后把尾部元素填到堆顶再做 adjust 调整（向下下沉）”，而不是直接重排整个堆；进队时是“插到尾部再向上调整”，两者调整方向相反。
向上调整的终止条件有两个：新结点不小于父结点，或祖先结点已到根；二者满足其一即停止。

2.9 基数排序（Radix Sort）

多关键字排序（思想基础）

前面介绍的排序都是按单一关键字进行的；例如每个元素是一个学生的数据，若按学号排序，学号即其关键字。

有时需要按多个关键字排序，例如学生数据先按年龄排序、年龄相同者再按身高排序，这称为多关键字排序。

多关键字排序中关键字有主次之分：排序中先考虑的关键字称为主关键字，其余称为次关键字。在"先按年龄再按身高"的示例中，年龄是主关键字、身高是次关键字。

多关键字排序的结果示例（先按第一关键字、第一关键字相同再按第二关键字有序）：

排序前：(19,165), (20,167), (18,170), (20,160), (19,172) 排序后：(18,170), (19,165), (19,172), (20,160), (20,167)

核心思想

基数排序（也称口袋排序）基于多关键字排序的思想，用来解决单一关键字排序问题。

具体方法：把单一关键字中的不同位数视作多关键字进行排序。

以原始序列 $18,\ 26,\ 31,\ 72(a),\ 8,\ 15,\ 88,\ 72(b),\ 35,\ 20$ 为例，这些数有十位和个位两位数字，处理顺序可有两种选择。

最高位优先法 MSD（Most Significant digital）：先看十位再看个位。
低位优先法 LSD（Least Significant Digital）：先看个位再看十位。

最高位优先法 MSD

方法：先根据十位上的值按序将数据分到 10 个不同子序列中；然后对每个子序列中的数据再按个位分到 10 个子序列中；最后将各个子序列顺序连接起来，便得到最终的有序序列。

第一步（按十位分到 10 个子序列）：同一子序列内元素的十位相同，且子序列按十位由小到大排列（如十位为 0 放入子序列 0、十位为 1 放入子序列 1，依此类推），相等键 $72(a)$ 、 $72(b)$ 落入同一子序列且保持原相对次序。

第二步：每个子序列再单独按个位数值排序，即在每个子序列内部又分裂出若干"子子序列"。

第三步：将所有子序列（及其内部已按个位排好的子子序列）按序连接起来，形成最终有序序列 $8,\ 15,\ 18,\ 20,\ 26,\ 31,\ 35,\ 72(a),\ 72(b),\ 88$ 。

MSD 的代价：如果数字有 $m$ 位，就有 $m$ 层（逐层向下分裂子序列），比较复杂。

低位优先法 LSD

方法：先将原始序列根据个位数值按序分割成 10 个子序列，然后将这 10 个子序列收集形成一个新的序列；再次将该新序列按照十位数值按序分割成 10 个子序列，将 10 个子序列按序连接后便得到最终的有序序列。

第一趟（按个位）分配与收集：按个位把元素放入编号 0–9 的 10 个口袋（口袋 0 放 20，口袋 1 放 31，口袋 2 放 72(a)、72(b)，口袋 5 放 15、35，口袋 6 放 26，口袋 8 放 18、8、88，其余为空），再按口袋编号从小到大顺次收集成新序列；相等键 $72(a)$ 、 $72(b)$ 入同一口袋并保持原次序。本趟收集后序列变为 $20,\ 31,\ 72(a),\ 72(b),\ 15,\ 35,\ 26,\ 18,\ 8,\ 88$ 。

第二趟（按十位）分配与收集：在上一趟收集结果上按十位再分配（口袋 0 放 8，口袋 1 放 15、18，口袋 2 放 20、26，口袋 3 放 31、35，口袋 7 放 72(a)、72(b)，口袋 8 放 88，其余为空）、再收集，得到最终有序序列 $8,\ 15,\ 18,\ 20,\ 26,\ 31,\ 35,\ 72(a),\ 72(b),\ 88$ 。

LSD 的代价：如果数字有 $m$ 位，只需进行 $m$ 趟的分配和收集，相对简单。

LSD 与 MSD 的区别（为何采用 LSD）

LSD 和 MSD 的不同之处在于：按个位数值分割得到的子序列不再各自进一步分割成子子序列，而是按序收集后统一参加下次按十位数值的分割；无论是存储还是处理都变得更加便捷简单。

基数排序法采用 LSD 方法，基于若干次的分配和收集：每次分配都是将元素分配到若干个不同的口袋中，每次收集都是将若干个口袋中的元素顺次收集成新的序列；因此基数排序又称为口袋排序法。

复杂度分析

10 个口袋是根据每位数字的所有取值定出的，和元素的个数没有关系。

和元素个数相关的是两趟分配工作：每趟分配的时间复杂度是 $O(n)$ ；将最后一趟收集结果写回数组的时间消耗也是 $O(n)$ 。

每次收集工作的时间消耗都是常量次数 10。

设元素的最大值位数为 $m$ ，分配、收集要各自进行 $m$ 趟，故整个算法的复杂度为 $O(mn)$ 。

易错点

口袋（子序列）数量取决于每位数字的取值范围（十进制为 10 个），与待排元素个数 $n$ 无关，不要把口袋数与 $n$ 混淆。

收集时必须按口袋编号由小到大、同一口袋内按入袋的原有先后顺序顺次收集，否则会破坏已排好低位的有序性（如示例中 $72(a)$ 、 $72(b)$ 的相对次序需保持）。

应采用 LSD（低位优先）实现：MSD 需逐层分裂出子子序列、有 $m$ 层、存储与处理都更复杂；LSD 只需 $m$ 趟分配与收集，统一收集后再参加下一位分割，更便捷。

2.10 内排序小结与牛刀小试

牛刀小试

例题一：最差时间复杂度为 $O(n\log n)$ 的算法计数

题目：直接选择排序、堆排序、快速排序、基数排序中，最差时间复杂度是 $O(n\log n)$ 的有几个？选项 A. 1 B. 2 C. 3 D. 4。

幻灯片标注答案为 A，即 1 个。

判断要点：需逐一比对四种算法（直接选择排序、堆排序、快速排序、基数排序）的"最差时间复杂度"是否等于 $O(n\log n)$ ，再统计满足条件的个数。

例题二：从百万乱序整数中选出最小的 k=100 个

题目：要在 $n=1000000$ 个乱序整数中找出最小的 $k=100$ 个整数，使用下列哪个算法速度最快？前提说明：无需完整执行排序算法，只要完成所需任务即可提前退出排序算法。选项 A. 归并排序 B. 冒泡排序 C. 基数排序 D. 堆排序。

幻灯片标注答案为 D，即堆排序。

判断要点：题目允许在"完成所需任务"后提前退出排序，因此应选择能够支持提前终止、只需局部完成即可取得最小 $k$ 个元素的算法。

例题三：补全满足稳定性要求的二分插入排序

题目：请补充如下满足稳定性要求的二分插入排序算法，实现关键字从小到大的排序功能。

幻灯片左侧给出的数据结构定义与待补全算法模板（三处空缺以 ____ 标出）：

代码

template <class KEY, class OTHER>
struct SET {
    KEY key;
    OTHER other;
};

template <class KEY, class OTHER>
void binaryInsertSort(SET<KEY, OTHER> array[], int size) {
    int low, mid, high, i;
    SET<KEY, OTHER> tmp;
    for (i = 1; i < size; i++) {
        low = 0; high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if ( ____ )
                low = mid + 1;
            else
                ____ ;
        }
        if ( low < i ) {
            tmp = array[i];
            for ( ____ ) {
                array[j] = array[j - 1];
            }
            array[low] = tmp;
        }
    }
}

幻灯片右侧给出的三处填空答案（依模板中三处 ____ 自上而下对应）：

第一处 if 条件：array[mid].key <= array[i].key。条件成立时执行 low = mid + 1，即向右半区继续查找插入位置。
第二处 else 分支（即上述条件不成立时）：high = mid - 1，向左半区继续查找。
第三处后移循环 for 头：int j = i; j > low; j--，由后向前依次将元素后移以空出插入位置 low。

稳定性要点：二分查找插入位置时使用 <=（而非 <）作比较，当 array[mid].key 等于待插入元素 array[i].key 时条件成立，使 low = mid + 1 把查找区间推向右侧，最终插入位置位于已有相等关键字元素之后，从而保持相等关键字元素的相对次序不变，满足稳定性要求。

三、外排序

3.1 外排序基本概念

外排序的定义

外排序是指元素个数太多、无法一次性载入内存的排序情形。由于数据处理要求首先把数据载入内存，因此需要在内存与外存之间进行多次数据交换。

外存数据载入内存、与内存中数据处理相比，速度要慢得多；因此外排序时间的耗费主要体现在对外存的访问上。

基本思路：分段内排序 + 有序段归并

数据交换时的规模取决于内存的大小。直观的做法是根据内存容量的大小，一次调入一定量的数据，形成一个数据序列；该序列在内存中可以按照某种内排序的方法进行排序，然后将排好的序列写入外存，之后再调入其他未排序的数据，以此类推。

最终在外存上，原始的待排序序列被分割成了多个有序序列；之后再设法将数据分段调入内存，进行有序数据段的归并。

设备依赖性

外排序具有设备依赖性，主要涉及两类外存设备：磁带存储器与磁盘存储器。

磁带存储器的特性：

顺序存取设备。
完成有效的排序至少需要两个磁带机。
三个磁带机可以简化问题。

磁盘存储器的特性：

随机存取设备。
存储层次结构：柱面 –> 盘片 –> 磁道 –> 扇区 –> 页面。

在外存上进行排序的核心考虑

外排序主要考虑的问题是：如何减少外存储器的读写？

在外存上进行排序：

常用方法：归并排序（访问序列中第一元素）。
非常适合：顺序文件（磁带存储器）。

外排序的两个阶段

外排序分为两个阶段：预处理与归并。

预处理阶段：

将 $N$ 个记录分批读入内存。
通过各种内排序算法，形成有序片段。

归并阶段：

把这些有序片段归并为一个有序文件。

易错点

外排序的性能瓶颈在外存访问而非内存中的比较/移动，因此衡量与优化的重点是减少外存读写次数，而不是内存中的操作量。
归并排序之所以适合外存，是因为它每次只需访问序列中的第一个元素，契合磁带这类顺序文件的存取方式。

3.2 K 路归并与多阶段归并

预处理阶段（产生初始已排序片段）

最简单的方法：按照内存容量尽可能多地读入数据记录，在内存进行排序，排序的结果写入文件，形成一个已排序片段。需注意的两点规律：每次读入记录数越小，形成的初始已排序片段越多；已排序片段越多，归并次数越多。

核心思想

最简单的归并是二路归并，二路归并是将两个有序序列归并为一个有序序列。在外排序中，二路归并需要 4 条磁带：最初无序序列在一条磁带上（如 A1），分段入内存排序后放到 B1、B2 两条磁带上，后面逐次进行二路归并。如果有 $2K$ 个磁带，就可以实现 $K$ 路归并。

K 路归并过程演示（以二路归并为例，4 条磁带 A1、A2、B1、B2）

幻灯片用分镜 (a)–(e) 演示二路归并的逐趟推进，每一趟从两条源磁带各取有序片段进行二路归并并写到目标磁带，下一趟源、目标互换；随着归并进行，片段不断变长、片段数不断减少。

各趟磁带状态如下（| 分隔同一磁带上的不同已排序片段）：

(a)：A1、A2 为空；B1：5, 22 | 3, 70 | 6, 13 | 4；B2：11, 50 | 19, 51 | 9, 17。
(b)：A1：5, 11, 22, 50；A2：3, 19, 51, 70；B1：6, 13 | 4；B2：9, 17。
(c)：A1：5, 11, 22, 50 | 6, 9, 13, 17；A2：3, 19, 51, 70 | 4；B1、B2 为空。
(d)：A1、A2 为空；B1：3, 5, 11, 19, 22, 50, 51, 70；B2：4, 6, 9, 13, 17。
(e)：所有元素归并成一条磁带上的单一有序序列 A1 : 3, 4, 5, 6, 9, 11, 13, 17, 19, 22, 50, 51, 70，归并完成。

结论：如果有 $2K$ 个磁带，就可以实现 $K$ 路归并。

K 路归并例子（置换选择产生初始片段后的磁带配置）

幻灯片用序列 81, 94, 11, 96, 12, 35, 17, 99, 28, 58, 41, 75, 15 演示，关键观察如下：

初始时磁带配置：数据在一条磁带 A1 上为 81, 94, 11, 96, 12, 35, 17, 99, 28, 58, 41, 75, 15，A2、B1、B2 为空。
经"置换选择"后，A1 重排为 11, 81, 94, 96, 12, 17, 28, 35, 41, 58, 75, 99, 15。
长度 =8 的已排序片段分布在两条磁带上：B1 为 11, 81, 94, 96 与 15 两段，B2 为 12, 17, 28, 35, 41, 58, 75, 99。

多路归并优化：多阶段归并

K 路归并策略需要 $2K$ 条磁带，这可能限制了它某些应用。如果只有 $k+1$ 个磁带，利用多阶段归并也可以进行 $k$ 路归并。

多阶段归并的一般过程（设 $k+1$ 个磁带，分别为 A、B1、B2、…、Bk）：

将分别来自 B1、B2、…、Bk 的 $k$ 个有序序列进行 $k$ 路归并为一个有序序列，放入 A。
之后再从 B1、B2、…、Bk 分别取下一个有序序列进行 $k$ 路归并为一个有序序列，继续放入 A。
如此操作，直到某个磁带 Bi 中没有有序序列，此时又变成 $k$ 个磁带上有有序序列、一个磁带上没有有序序列的情况；按照上面的方法从 $k$ 个有数据的磁带上继续逐次进行 $k$ 路归并到空磁带上。
最后直到只有一个磁带上有数据，该数据序列是一个有序序列。这一方法称多阶段归并。

3+1 磁带实现 3 路归并的演示

如果只有 $3+1$ 个磁带，利用多阶段归并也可以进行 3 路归并。幻灯片用一张表格记录 4 个磁带（T1、T2、T3、T4）在不断归并过程中每个磁带上归并段（Runs）数量的变化；每一次操作都是将数据从 3 个有数据的磁带合并到那 1 个空磁带上。

磁带	Runs 变化（每列为一趟归并后的归并段数，空白表示该磁带当前为空）
T1	（空）, 8, 3, （空）, 2, 1, （空）, 1
T2	8, （空）, 5, 2, （空）, 1, （空）, （空）
T3	13, 5, （空）, 3, 1, （空）, 1, （空）
T4	21, 13, 8, 5, 3, 2, 1, （空）

多阶段归并例子（3 条磁带、34 个初始归并段）

假设三条磁带 T1、T2、T3，在 T1 上的输入文件有 34 个已排序的归并段，问第一步该怎么做才能用多阶段归并。

按均匀的方法（直观方法，行不通）

平分 34 个已排序片段（直观方法）：在 T2 和 T3 上各自放 17 个已排序片段，然后归并到 T1；但要把其中一部分放到 T2 上以进行另一次归并（即没法直接继续合并了）。

按不均匀的方法（正确思路）

分解原来的 34 个已排序片段，使分布不均匀。

如在 T2、T3 上分别放 21、13 个已排序的片段。
在 T3 为空以前，能归并 13 个已排序片段到 T1 上。
分别将 T1、T2 上的 13、8 个已排序片段归并到 T3 上。

斐波那契分布与归并过程表

如果已排序片段的数目是一个斐波那契数 $F_N$ ，那么分布最好的方法就是把它们分解为 2 个斐波那契：

F_N = F_{N-1} + F_{N-2}

以 $34 = 21 + 13$ 为例，初始时 T1 为 0、T2 放 21、T3 放 13，前两步归并操作（"执行的操作"列标注本步参与归并的磁带对，结果写到第三条）如下表：

磁带	已排序片段数	T2+T3	T1+T2
T1	0	13	5
T2	21	8	0
T3	13	0	8

完整归并到底的过程（沿用 $34 = 21 + 13$ 的初始分布，逐步轮换参与归并的磁带对，直至只剩一条磁带有数据）如下表，列头依次为每一步参与归并的磁带对：

磁带	已排序片段数	T2+T3	T1+T2	T1+T3	T2+T3	T1+T2	T1+T3	T2+T3
T1	0	13	5	0	3	1	0	1
T2	21	8	0	5	2	0	1	0
T3	13	0	8	3	0	2	1	0

适用条件与易错点

若已排序片段的数目不是斐波那契数，为了将已排序片段数达到一个斐波那契数，必须在磁带上填充虚拟的已排序片段。
把片段在两条源磁带上平均分配（17/17）看似直观，却会导致一趟归并后无法直接继续，是错误的分布方式；片段应按斐波那契数不均匀分布。
多阶段归并用 $k+1$ 条磁带实现 $k$ 路归并，相比 K 路归并所需的 $2K$ 条磁带更省磁带。

3.3 置换选择（Replacement Selection）

动机：为什么要拉长初始片段

对有 $m$ 个初始归并段的 $k$ 路归并，其归并趟数（进而主要 I/O 时间）与 $\log_k m$ 成正比， $m$ 越小时间花费越小。

由此，置换选择通过拉长每个有序序列（初始归并段）的长度来减少初始归并段的个数 $m$ 。

直观说明：要排序 1000 个数据时，若切成 100 个长度为 10 的小片段，则需要归并很多次才能把这 100 个片段合并成 1 个；若切成 10 个长度为 100 的大片段，归并的次数就会大大减少。

结论：初始片段越长，生成的片段总数就越少，后续归并时读写磁盘的次数就越少，排序也就越快。

核心思想

假设计算机内存很小，一次只能装下 3 个数字（内存容量 $p=3$ ）。最朴素的做法是：读 3 个数字进内存，排好序，写回磁盘；再读 3 个，排好序，写回磁盘。这样得到的每个片段长度永远刚好是 3（也就是 $p$ ）。

如能让每个初始已排序的片段包含更多的记录，就可以减少排序时间。置换选择可以在只能容纳 $p$ 个记录的内存中生成平均长度为 $2p$ 的初始已排序片段（即置换选择可以生成比内存容量更大的排序片段）。

如何更有效构造已排序片段，关键观察有两点：

当一个元素写到输出磁带上时，其内存空间便空出，可以读入其他元素。
如果输入磁带上的下一个元素不小于刚刚的输出元素，就可以把它放入这个已排序片段。

过程要点

每一步从内存（容量 $p$ ）中选出当前的最小值输出到当前片段；输出后空出的位置立即从输入读入一个新元素。

判断新读入的元素归属：

若新读入的元素不小于刚输出的元素，它可以继续放入当前正在生成的片段。
若新读入的元素比刚输出的元素小，则它无法进入当前片段，应留待下一个片段（在示例中以灰底标出），当前片段中剩余的可用元素全部输出完后，再开始下一个片段。

正因为可以不断把"不小于刚输出元素"的新元素纳入当前片段，所以生成的片段平均长度可达 $2p$ ，超过内存容量 $p$ 。

选最小值的实现与复杂度

数据读入内存中后，每次都只是找最小值。

朴素做法：输出一个元素后，在该元素空出的位置上再读入一个新数据，若内存中当前维护 $p$ 个记录，最小值的选择只能逐个比对，时间消耗为 $O(p)$ 。
最小化堆做法：内存中元素按最小化堆存储，输出元素总是下标为 0 的元素；新读入的元素先放入空出的位置，紧接着对它进行调整，使整个序列仍然保持堆结构，时间消耗为 $O(\log_2 p)$ 。

置换选择过程示例（待读入序列）

对待读入序列 $3, 8, 5, 6, 2, 0, 9, 4, 1, -5$ 、内存可容纳 3 个记录（ $a(0), a(1), a(2)$ ）做置换选择，逐行追踪"内存中、待读入序列、已输出的有序序列"三栏的变化，最终生成的有序片段依次为：

第 1 段： $3, 5, 6, 8, 9$ （长度 5，已超过内存容量 3）。
第 2 段： $0, 1, 2, 4$ 。
第 3 段： $-5$ 。

追踪中被灰底标出的内存元素（如 $2, 0, -5$ ）即"比当前片段已输出值小、无法并入当前片段"的元素，被留到后续片段。

已排序片段构建示例（优先队列）

设文件上的数据为 $81, 94, 12, 11, 96, 35, 17, 99, 28, 58, 41, 75, 15$ ，内存中能容纳 3 个记录（归并路数为 3 个），用优先队列组织内存中的 $a[1], a[2], a[3]$ 。

逐帧规律（不必逐一抄数字）：

初始装入 $a[1]=12, a[2]=94, a[3]=81$ ，第 1 个片段（列标"1"）开始构建。
每一步输出当前内存中的最小值（进入"输出"行），并从"输入"行读入文件的下一个数据补到空位。例如第 1 帧输出最小值 $12$ （绿底）后读入 $11$ （黄底）。
关键判断：新读入的元素若小于本片段已输出的最大值（如 $11 < 12$ ），则该元素以灰底标出、不能进入当前片段（如 $11$ 、随后读入的 $35$ 均被灰底标出，留给下一片段）；若不小于则可继续并入当前片段（如读入的 $96$ 进入第 1 片段）。
因而第 1 片段的输出序列保持递增（ $12, 81, 94, \dots$ ），其长度可超过内存容量 3；被留下的较小元素（如 $11, 35$ ）将构成后续片段。

可迁移的判断要点：始终输出内存最小值；每输出一个就补读一个；新元素若不小于当前片段已输出最大值则入本段，否则留到下一段；当内存中已无可加入当前段的元素时，结束当前段、开启下一段。

牛刀小试（含给出的答案）

对序列 $\{10, 5, 22, 13, 7, 9, 15, 8, 12, 4, 1, 2, 3, 11, 6, 14, 20, 19, 18, 17, 16, 21\}$ ，内存大小 $w=7$ ，用置换选择法处理后的结果为两个有序片段：

第一段： $5, 7, 8, 9, 10, 12, 13, 15, 22$ （长度 9，已超过内存容量 7）。
第二段： $1, 2, 3, 4, 6, 11, 14, 16, 17, 18, 19, 20, 21$ （长度 13）。

该例验证了置换选择能生成长度超过内存容量 $w$ 的初始片段，两段长度之和恰为输入个数 22。

易错点

示例中内存容量 $p$ 等于归并路数（ $p=3$ ，归并路数为 3）；初始装入内存的就是文件最前面的 $p$ 个记录。
判断新元素能否进入当前片段，比较对象是当前片段已输出的元素，而不是固定阈值；不小于刚输出元素才能并入。
朴素逐个比对找最小值的代价是 $O(p)$ ，用最小化堆才能降到 $O(\log_2 p)$ ；这里的 $p$ 是内存中维护的记录数，不要与初始归并段个数 $m$ 混淆。

优化

用最小化堆（优先队列）维护内存中的记录：输出下标为 0 的最小元素，新读入元素放入空出位置后进行调整恢复堆结构，使单次选最小值由 $O(p)$ 降为 $O(\log_2 p)$ 。

3.4 k 路归并排序（k-way merge sort）

题目要求实现一个多路归并排序算法，合并 k 个有序子序列，需满足三点：(1) 递归地将数组划分为 k 个子数组；(2) 对每个子数组递归进行多路归并排序；(3) 尽可能快地合并 k 个有序子数组。

实现结构分三层：包装函数 kWayMergeSort(a, n, k) 负责对外接口并调用递归接口；递归函数 kWayMergeSort(a, low, high, k) 负责划分与递归；合并函数 kWayMerge(...) 负责把 k 个有序子段归并为一段。

划分要点：算法前提是 k >= 2，否则递归划分不会缩小区间；实际可划分的子数组个数取 actual_k = min(k, len)（保证不超过区间长度，且不超过 k）；用 base = len / actual_k 与 remainder = len % actual_k 把多出的余数分摊到前若干段，使前 remainder 段长度多 1，从而各段长度尽量均匀。

合并要点：用最小堆（priority_queue 实现的 min_heap，元素为 HeapElement，按 Compare 比较）来做 k 路归并；先把每个子段的首元素入堆，每次弹出堆顶（当前最小元素）写入临时数组，再把该元素所在子段的下一个元素（若存在）入堆，直到堆空，最后把临时数组复制回原数组。

代码

// 包装函数及数据接口格式
template <class elemType>
void kWayMergeSort(elemType a[], int n, int k) {
    kWayMergeSort(a, 0, n - 1, k);
}

// 递归函数的接口格式
template <class elemType>
void kWayMergeSort(elemType a[], int low, int high, int k) {
    int len = high - low + 1;
    if (len <= 1) return;  // 单元素区间已有序

    // 计算实际划分的子数组个数（不超过 k）
    int actual_k = min(k, len);

    // 计算每个子数组的长度
    int base = len / actual_k;
    int remainder = len % actual_k;

    // 创建起始和结束位置数组，此处未必需要使用 vector，只要是合理的数据结构都可以
    vector<int> starts(actual_k);
    vector<int> ends(actual_k);

    // 划分区间
    int current = low;
    for (int i = 0; i < actual_k; i++) {
        int sub_len = base + (i < remainder ? 1 : 0);
        starts[i] = current;
        ends[i] = current + sub_len - 1;
        current = ends[i] + 1;
    }

    // 递归排序每个子数组
    for (int i = 0; i < actual_k; i++) {
        kWayMergeSort(a, starts[i], ends[i], k);
    }

    // 合并 k 个有序子数组
    kWayMerge(a, low, high, actual_k, starts, ends);
}

代码

template <class elemType>
void kWayMerge(elemType a[], int low, int high, int k,
               const vector<int>& starts, const vector<int>& ends) {
    int len = high - low + 1;
    elemType* temp = new elemType[len];  // 创建临时数组存储合并结果

    // 使用最小堆合并 k 个有序子数组
    priority_queue<HeapElement, vector<HeapElement>, Compare> min_heap;

    // 初始化堆：将每个子数组的第一个元素加入堆（此处若使用的不是堆，且是普通队列或者排序方法，会更慢）
    for (int i = 0; i < k; i++) {
        if (starts[i] <= ends[i]) {
            min_heap.push({a[starts[i]], i, starts[i]});
        }
    }

    int idx = 0;  // 临时数组索引
    while (!min_heap.empty()) {
        HeapElement top = min_heap.top();
        min_heap.pop();
        temp[idx++] = top.value;  // 将最小元素加入临时数组

        // 从当前子数组取下一个元素（如果存在）
        int next_pos = top.pos + 1;
        if (next_pos <= ends[top.array_idx]) {
            min_heap.push({a[next_pos], top.array_idx, next_pos});
        }
    }

    // 将合并结果复制回原数组
    for (int i = 0; i < len; i++) {
        a[low + i] = temp[i];
    }

    delete[] temp;  // 释放临时数组
}

k 路归并合并阶段宜用最小堆（优先队列）取各段当前最小元素；若使用的不是堆，而是普通队列或排序方法，会更慢。

四、本章小结

排序的地位与分类

排序是数据存储后支持快速查找最重要的操作。

排序根据数据的规模分为两种：当数据量不大、能一次性全部载入内存时，可利用内部排序的方法；当数据量大、内存中只能存下部分数据、需要多次进行内外存之间数据的读写时，可利用外部排序的方法。

常见的内部排序方法有很多，如冒泡排序、插入排序、归并排序、快速排序、选择排序、堆排序、基数排序。衡量一个内部排序的算法除了看时间、空间复杂度，还要看算法是否是稳定排序。

内部排序时间复杂度对比

冒泡排序、插入排序、选择排序、快速排序的最坏情况下时间复杂度都是 $O(n^2)$ 。

特别地，在数据原本正序的基础上，冒泡排序和插入排序的时间复杂度可以达到 $O(n)$ 。

基数排序在最大位数 $m$ 可视为常数时可看作 $O(n)$ ；堆排序的一般和最坏时间复杂度为 $O(n\log_2 n)$ 。

归并排序、堆排序最坏情况、快速排序最好情况下，时间复杂度能达到 $O(n\log_2 n)$ 。

内部排序稳定性对比

冒泡排序、插入排序、归并排序、基数排序都是稳定排序。

而快速排序、希尔排序、选择排序、堆排序都是不稳定排序。

外部排序要点

外部排序采用分批将数据载入内存，经过内部排序后形成若干个初始归并段（有序子序列），然后再利用归并的方法，最终形成一个有序序列；其时间消耗主要体现在内外存的数据读写上。

在形成初始归并段阶段，利用置换选择方法可以拉长每个归并段长度，达到减少归并段数量的目的。

如果归并采用 k 路，除了可以用 $2k$ 个磁带，也可以仅用 $k+1$ 个磁带来解决。

第七章 排序

一、排序概念

为什么要排序

关键字（排序依据）

排序的稳定性

内排序与外排序

排序的基础操作与默认约定

二、内排序

2.1 冒泡排序（Bubble Sort）

核心思想

过程示例（数值演示的一般规律）

C++ 代码实现

优化

稳定性

复杂度分析

易错点

2.2 插入排序（Insertion Sort）

核心思想

单次插入的过程要点

单元素插入的 C++ 代码

整体插入排序的 C++ 代码

排序过程的关键观察

复杂度分析

稳定性

2.3 希尔排序（Shell Sort）

核心思想

子序列划分与过程要点

C++代码

复杂度分析

稳定性

2.4 归并排序（Merge Sort）

核心思想

两路归并（merge）的过程要点

在数组中归并的存储约定

C++代码：merge

C++代码：mergeSort（递归分治）

分割与合并示例

时间复杂度分析

稳定性

2.5 快速排序（Quick Sort）

核心思想

分割（partition）过程要点

C++ 代码

时间复杂度分析

稳定性

易错点与实现约定

优化方法

2.6 选择排序（Selection Sort）

核心思想

过程要点（数值演示的一般规律）

C++ 代码

复杂度分析

稳定性

易错点

2.7 堆排序（Heap Sort）

堆的概念

核心思想

过程要点（建堆与摘取演示）

C++ 代码

时间复杂度分析

稳定性分析

易错点

2.8 优先队列（Priority Queue，堆的应用）

核心思想

为什么用堆实现（与线性结构对比）

出队操作

进队操作

复杂度小结

易错点

2.9 基数排序（Radix Sort）

多关键字排序（思想基础）

核心思想

最高位优先法 MSD

低位优先法 LSD

LSD 与 MSD 的区别（为何采用 LSD）

复杂度分析

易错点

2.10 内排序小结与牛刀小试

牛刀小试

例题一：最差时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn) 的算法计数

第七章排序

例题一：最差时间复杂度为 $O(n\log n)$ 的算法计数