排序的基本概念

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

排序的确切定义如下：

输入：n 个记录 $R_{1}, R_{2}, \dots, R_{n}$ ，对应的关键字为 $k_{1}, k_{2}, \dots, k_{n}$
输出：输入序列的一个重排 $R_{1}^{'}, R_{2}^{'}, \dots, R_{n}^{'}$ ，使得 $k_{1}^{'} \leq k_{2}^{'} \leq \dots \leq k_{n}^{'}$ （其中“<”可以换成其他的比较大小的符号）
算法的稳定性：若排序后两个关键字相等的元素的相对位置不变，则称排序算法是稳定的，否则称排序算法是不稳定的
算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述
如果待排序表中的关键字不允许重复，那么选择排序算法时的稳定与否就无关紧要
注意：对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可

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

内部排序，是指在排序期间元素全部存放在内存中的排序
外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序

一般情况下，内部排序算法在执行过程中都要进行两种操作：

比较：通过比较两个关键字的大小，确定对应元素的前后关系
移动：确定号前后关系后通过移动元素以达到有序

并非所有的内部排序算法都要基于比较操作，基数排序就不基于比较

每种排序算法都有各自的优缺点，适合在不同的环境下使用

通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序、基数排序五大类

内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的

选择题：对任意 n 个关键字进行基于比较排序，至少需要进行 $⌈ \log_{2} (n!) ⌉$ 次关键字之间的两两比较

插入排序

直接插入排序

假设待排序表在某次过程中属于这种情况，待排序表 L[1...n] 在某次排序过程中某一个时刻状态如下：

要为了实现将元素 L(i) 插入到已有序的子序列 L[1…i−1] 中，需要执行以下操作（L[] 表示一个表，L() 表示一个元素）：

查找出 L(i) 在 L[i+1…n] 中的插入位置 k
将 L[k…i−1] 中所有元素全部后移一个位置
将 L(i) 赋值到 L(k)


void InsertSort(int A[],int n) {

    int i, j;

    for (i = 2; i <= n; i++) {  // 把 2 ~ n 的元素插到前面

        if (A[i] < A[i - 1]) {  // 如果小于它前驱就开始插入操作

            A[0] = A[i];

            for (j = i - 1; A[0] < A[j]; j--)  // 一边查找一边向后移动

                A[j + 1] = A[j];

            A[j + 1] = A[0];

        }

    }

}

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

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

时间效率：

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为 O(n)
在最坏情况下，当初始序列为逆序时，总的比较次数达到最大，为 $\sum_{i = 2}^{n} i$ ；总的移动次数也达到最大，为 $\sum_{i = 2}^{n} (i + 1)$
平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 $n^{2} / 4$ ，直接插入排序算法的时间复杂度为 $O (n^{2})$

稳定性：直接插入排序是稳定的。插入元素时总是从后向前先比较再移动，不会出现相同元素相对位置发生变化的情况

适用性：直接插入排序算法适用于顺序存储和链式存储的线性表

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

选择题：将 n 各不同的元素进行直接插入排序，最多需要进行的比较次数是 $\frac{n (n - 1)}{2}$ ，最少比较次数是 $n - 1$

折半插入排序

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

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

下面将比较和移动操作分离开，即先折半查找出元素的待插入位置，然后再统一的移动待插入位置之后的元素

当排序表为顺序表时，查找有序子表时可以用折半查找来实现，确定待插入位置后，就可统一地向后移动元素

算法代码如下:


void InsertSort(int A[], int n) {

    int i, j, low, high, mid;

    for(i = 2; i <= n; i++) {

        A[0] = A[i];

        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})$ ，但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能

折半插入排序是一种稳定的排序方法

考点追踪：直接插入与希尔排序的特性（2012、2014、2015、2018、2025）

直接插入排序在基本有序时效率极高（ $O (n)$ ）。2. 希尔排序是不稳定的，增量序列的选择决定了性能。3. 折半插入仅减少了比较次数，未减少移动次数。

希尔排序

当插入排序排序基本有序的排序表和数据量不大的排序表时较快，希尔排序是基于这两点分析改进而来的

希尔排序的基本思想是：

把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈基本有序时，再对全体记录进行一次直接插入排序
如 5, 6, 2, 9, 8, 3, 4, 1 取 3 为增量可以有子表 5, 9, 4 和 6, 8, 1 和 2, 3，对它们进行排序后，就会更加的有序

希尔排序的过程如下：

先取一个小于 n 的步长 $d_{1}$ ，把表中的全部记录分成 $d_{1}$ 组，所有距离为 $d_{1}$ 的倍数的记录放在同一组
在各组内进行直接插入排序，然后取第二个步长 $d_{2} < d_{1}$ ，重复上述过程，直到所取到的 $d_{t} = 1$
所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快得到最终结果

目前为止尚未求得一个最好的增量序列，常用的方法是 $d_{1} = n / 2$ ， $d_{i + 1} = ⌊ d_{i} / 2 ⌋$ ，并且最后一个增量等于1


void ShellSort(int A[],int n) {

    for (int dk = n / 2; dk >= 1; dk = dk / 2)  // 步长变化

        for (int i = dk + 1; i <= n; i++)  // 对子列进行插入排序

            if (A[i] < A[i - dk]) {

                A[0] = A[i];

                for(int j = i - dk; j > 0 && A[0]; j = j - dk)

                    A[j + dk] = A[j];

                A[j + dk] = A[0];

            }

}

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

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

时间效率：当 n 在某个特定范围时，希尔排序的时间复杂度约为 $O (n^{1.3})$ ；在最坏情况下希尔排序的时间复杂度为 $O (n^{2})$

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

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

交换排序

冒泡排序

冒泡排序的算法思想是：

从后往前（或从前往后）两两比较，逆序就交换，直到序列比较完
我们称之为一趟冒泡，结果将最小或最大的元素交换到待排序的第一个位置
在下一趟冒泡的时候，上一趟确定的元素不需要比较，待排序列减少一个元素
每一趟都会把序列中最小（或最大）元素放到序列的最终位置


void BubbleSort(int A[], int n) {

    for (int i = 0; i < n - 1; i++) {

        flag = false;  // 本趟是否有交换，如没有交换表示以及有序

        for (int j = n - 1; j > i; j--)  // 进行一趟冒泡排序

            if (A[j - 1] > A[j]) {  // 如果你逆序就交换

                swap(A[j - 1], A[j]);

                flag = true;

            }

        if(flag == false)

            break;

    }

}

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

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

时间效率：

当初始序列有序时，显然第一趟冒泡后 flag 依然为 false，从而直接跳出循环，比较次数为 n - 1，移动次数为 0，从而最好情况下的时间复杂度为 O(n)
当初始序列为逆序时，需要进行 n - 1 趟排序，第 i 趟排序要进行 n - i 次关键字的比较，而且每次比较后都必须移动元素 3 次来交换元素位置
这种情况下，比较次数 $\sum_{i = 1}^{n - 1} (n - i)$ ，移动次数 $\sum_{3 (n - i)}^{n - 1} = \frac{3 n (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) 上，这叫一趟快速排序
分别递归的对两个子表重复上述过程，直至每部分内只有一个元素或者为空为止，即所有元素放在了其最终位置之上

先对表进行划分，而后对两个表调用同样的排序操作，因此可以递归的调用快速排序算法进行排序，具体的程序结构如下：


int Partition(ElemType A[], int low, int high) {  // 划分算法

    ElemType 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;  // 返回基准的位置

}



void QuickSort(int A[], int low, int high) {

    if (low < high) {  // 递归终止条件，表空

        int pivot = Partition(A, low, high);  // 划分

        QuickSort(A, low, pivot - 1);  // 依次对两个子表进行递归排序

        QuickSort(A, pivot + 1, high);

    }

}

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

空间效率：

快速排序是递归的，需要借助栈来保存每层递归调用的信息，其容量应与递归调用的最大深度一致
最好情况下，每次都从从中间分开，栈深度为 $O (\log_{2} n)$
最坏情况下，因为要进行 n - 1 次递归调用，所以栈的深度为 O(n)
平均情况下，栈的深度为 $O (\log_{2} n)$

时间效率：

快速排序的最坏情况发生在初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 $O (n^{2})$
当 Partition() 做到平衡的划分，得到的两个子问题的大小都不可能大于 n / 2，最好情况的时间复杂度为 $O (n \log_{2} n)$
快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，平均情况的时间复杂度为 $O (n \log_{2} n)$
快速排序是所有内部排序算法中平均性能最优的排序算法

有很多方法可以提高算法的效率：

尽量选取一个可以将数据中分的枢轴元素，如从序列的头中尾选取三个元素，再取这三个元素的中间值作为的枢轴元素
随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生

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

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

考点追踪：快速排序的过程、性能与划分（2010、2011、2014、2019、2023、2024）

基准元素的选取（如头、中、尾取中）影响性能。2. 递归深度与划分的平衡性有关，平均 $O (\log n)$ ，最坏 $O (n)$ 。3. 适合顺序存储，不适合链式存储。4. 每一趟排序至少能确定一个元素的最终位置。

核心结论：快速排序“确定位置”的判断（2019、2024）

每趟划分后，基准元素（枢轴）必定处于其最终排序位置。

判断方法：若一个元素左边的元素都比它小，右边的元素都比它大，则该元素可能是上一趟快排的枢轴（已入位）。

趟数：经过 $k$ 趟快排，至少有 $k$ 个元素入位。

综合应用题

奇偶分开

题目：已知线性表按顺序存储，且每个元素都是不相同的整数型元素，设计把所有奇数移动到所有偶数前面的算法（要求时间最少，辅助空间最少）

思路：从前面向后查找，找到偶数 L(i)；再从后面向前查找，找到奇数 L(j)，将 L(i) 和 L(j) 交换，反复直到 i > j

第 k 位置元素

题目：试编写一个算法，使之能够在数组 L[1...n] 中找出第 k 小的元素（即从小到大排序后处于第 k 个位置的元素）

思路：利用快排的会将枢轴（基准）元素放到其最终的位置上这一特性

选择子表第 1 位元素，进行划分算法操作，这时它在的 j 位置就是第 j 小的元素
比对 j和 k，若等于它就是第 k 小的元素
小于，把子表取左半部分，跳转步骤 1
大于，把子表取右半部分，跳转步骤 1

荷兰国旗

题目：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为 O(n) 的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案

思路：扫描线性表，将红色丢到前面；将蓝色丢到后面


typedef enum {RED, WHITE, BLUE} color;



void Flag_Arrange(color a[], int n) {

    // i 是红色指针前面全是红色；k 是蓝色指针后面全是蓝色；j 是工作指针

    int i = 0, j = 0, k = n - 1;

    while (j <= k) {

        switch (a[j]) {

            // 红色与 i 交换，当 i, j 不同时 a[i] 只会是白色

            case RED: swap(a[i], a[j]); i++; j++; break;

            case WHITE: j++; break;

            // 蓝色与 k 交换，因为不知道 a[k] 的颜色所有先不动 j

            case BLUE: swap(a[j], a[k]); k--; break;

        }

    }

}

选择排序

简单选择排序

简单选择排序算法的思想：假设排序表 L[1…n]，第 i 趟排序即从 L[i…n] 中选择关键字最小的元素与 L(i) 交换，每一趟排序可以确定一个元素的最终位置，这样经过 n − 1 趟排序就可以使整个排序表有序


void SelectSort(int A[], int n) {

    for (int i = 0; i < n - 1; i++) {  // n - 1 趟

        int Min = i;

        for (int j = i + 1; j < n; j++)  // 拿 L[i...n] 的最小值

            if (A[j] < A[Min])

                Min = j;

        if (Min != i)  // 把最小值与 L(i) 交换

            swap(A[i], A[Min]);  // 交换会移动三次元素

    }

}

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

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

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

稳定性：选择排序是一种不稳定的排序算法。如 L = {2, 2, 1} 排序后为 L = {1, 2, 2}

堆排序

堆

定义

堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将 L[1…n] 看做一棵完全二叉树的顺序存储结构，利用完全二叉树双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大

堆的定义如下，n 个关键字序列 L[1…n] 称为堆，当且仅当该序列满足以下任一条件：

L(i) ≤ L(2i) 且 L(i) ≤ L(2i + 1)
L(i) ≥ L(2i) 且 L(i) ≥ L(2i + 1)

满足 1 的称为小根堆（小顶堆），满足 2 的堆称为大根堆（大顶堆）

在大根堆中，最大元素存放在根结点中，且对其任一非根结点，它的值小于或者等于其双亲结点值；小根堆的定义刚好相反，根结点是最小元素

构建

n 个结点的完全二叉树，最后一个结点是第 $⌊ n / 2 ⌋$ 个结点的孩子

大根堆的构建（小根堆类似）：

对 $(⌊ n / 2 ⌋ \sim 1)$ 进行遍历进行以下操作（从最后非终端结点向上遍历）：
拿左右子树的最大值和本结点进行比较
如果没有子树或子树小于本结点进行下一轮循环
如果子树大于本结点则与较大值的子树交换
交换完后的子树可能比本结点大，所以转 2 继续比较交换


void HeapAdjust(ElemType A[], int k, int len) {

    A[0] = A[k];

    for (i = 2 * k; i <= len; i *= 2) {

        if (i < len && A[i] < A[i+1])  // 第二步，拿到较大值的子树

            i++;

        if (A[0] >= A[i]) break;  // 第三步，位置正确

        else {

            A[k] = a[i];  // 第四步，与较大值的子树交换

            k = i;  // 第五步，转回第二步继续比较交换

        }

    }

    A[k] = A[0];  // 把筛选点放入最终位置

 }



void BuildMaxHeap(ElemType A[], int len) {

    for(int i = len / 2; i > 0; i--)  // 第一步遍历

        HeapAdjust(A, i, len);

}

调整的时间与树高有关，为 O(h) 在建含 n 个元素的堆时，关键字的比较总次数不超过 4n，时间复杂度为 O(n)，这说明可以在线性时间内将一个无序数组建成一个堆

插入

将结点放入末端，再对这个新结点向上执行调整操作

删除

删除堆头元素后，拿数组最后的元素代替，再进行调整操作，代码就是 HeapAdjust()

堆排序

堆排序的思路：依次删除堆头，把删除的堆头构成序列就是排好序的序列

堆排序的过程：

将存放在 L[1...n] 中的 n 个元素构成堆
根据堆的特性，堆头就是最大值
把堆头的元素和最后一位的元素交换，那么最后位就变成最大值
调整堆，再拿堆头和倒数第二位的元素交换，依次类推就排序好了


void HeapSort(int A[], int len) {

    BuildMaxHeap(A, len);  // 构建堆

    for(int i = len; i > 1; i--) {

        swap(A[i], A[1]);  // 拿最后元素和堆头交换

        AdjustDown(A, 1, i - 1);  // 调整把 i - 1 个元素整理成堆

    }

}

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

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

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

稳定性：堆排序是一种不稳定的排序算法。表 L={1, 2, 2}，构造堆后 L={2, 1, 2}，排序后 L= {1, 2, 2}

考点追踪：堆的构造、调整与海量数据应用（2009、2011、2015、2018、2021、2022、2024）

建堆复杂度 $O (n)$ ，总排序 $O (n \log n)$ 。2. 插入/删除后的调整路径分析是常考点。3. 选出 $1$ 亿个数中的前 $100$ 个最大值，只需建大小为 $100$ 的小顶堆。

核心结论：堆的操作比较次数（2025 新焦点）

建堆：比较总次数不超过 $4 n$ ，时间复杂度 $O (n)$ 。

删除/插入：涉及调整，向下调整时每层比较 2 次（选左右大者，再与根比），深度为 $h$ ，故为 $O (h)$ 。

堆排序： $O (n \log n)$ ，且空间复杂度 $O (1)$ ，优于归并。

堆排序适合关键字较多的情况。例如，如何在 1 亿个数中选出前 100 个最大值？

首先使用一个大小为 100 的数组，读入前 100 个数，建立小顶堆

依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求

应用题：若只想得到一个序列中第 k（k $\geq$ 5）个最小元素之前的部分排序序列，则可以采用冒泡排序、堆排序、简单选择排序，当 $k \geq 5$ 时，选择堆排序最优

归并排序和基数排序

归并排序

归并的含义是将两个或者两个以上的有序表组合为一个新的有序表

假定待排序表中含有 n 个记录，则可以看为是 n 个有序的子表，每个子表长度为 1，然后两两归并，得到 $⌈ n / 2 ⌉$ 个长度为 2 或者 1 的有序表；再两两归并，直到合并为一个长度为 n 的有序表为止，这种排序方法称为 2 - 路归并排序

下面的 Merge() 的功能是将两个相邻的有序表归并位一个有序表：

新建个数组 B 复制要合并的数据
每次从对应 B 中的两段去取一个记录进行关键字的比较，将较小者放入 A 中
当数组B中有一段的下标超过其对应的表长时，将另一段中的剩余部分直接复制到 A 中

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

将待排序的元素分成两个子表
对左表排好序，对右表也排好序
把排好序的左右表合并


void Merge(int a[], int low, int mid, int high) {

    for (int i = low; i <= high; i++)  // 将 a 的要归并的元素复制到 b 中

        b[i] = a[i];

    // 归并，直到其中一个线性表为空

    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)

        if (b[i] <= b[j])

            a[k] = b[i++];

        else

            a[k] = b[j++];

    // 把另外的线性表放入

    while(i <= mid) a[k++] = b[i++];

    while(j <= high) a[k++] = b[j++];

}

 

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)，共需进行 $⌈ \log_{2} n ⌉$ 趟归并，所以算法的时间复杂度为 $O (n \log_{2} n)$

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

注意：一般而言，对于 N 个元素进行 k 路归并排序时，排序的趟数 m 满足 $k^{m} = N$ ，从而 $m = \log_{k} N$ ，又考虑到 m 为整数，所以 $m = ⌈ \log_{k} N ⌉$ ，其中 k 路归并就是每个拿 k 个表进行合并

考点追踪：归并与基数排序的中间过程（2013、2021、2022）

2 路归并的一趟过程分析。2. 基数排序的分配与收集（LSD vs MSD），且基数排序是稳定的。3. 掌握元素平均移动次数与初态无关的算法（如基数排序）。

基数排序

基数排序是一种很特别的排序方法，它基于关键字各位的大小进行排序

基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法

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

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

最高位优先（MSD）法，先按最高位的值对记录进行降序排序，再按次高位进行排序
最低位优先（LSD）法，先按最低位的值对记录进行升序排序，再按次低位进行排序

基数排序需要 r 个队列，排序过程有两个操作（通常采用链表基数排序）：

分配：根据当前关键字，把元素放入相应的队列里面
收集：把队列里面的元素依次首尾相接，得到新的线性表

基数排序的一趟操作就是进行一次分配和收集操作，操作实例如下动图（图是基于数组的）：

849589-20171015232453668-1397662527

基数排序算法的性能分析如下（链表）：

空间效率：一趟排序需要的辅助存储空间为 r 个队列，但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为 O(r)，对链表进行基数排序时，队列结点就是链表的结点，所以一个队列仅需要有队头和队尾指针

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

稳定性：基数排序是一种稳定的排序算法。对于基数排序算法而言，很重要一点就是按位排序时必须是稳定的

如果是数组实现的话：空间复杂度为 $O (r \cdot l e n)$ 桶个数乘桶长；时间复杂度为 O(d(n + n)) 收集操作也需要 O(n) 了

各种内部排序算法的比较及应用

内部排序算法的比较

从时间复杂度看：

简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为 $O (n^{2})$ ，且实现过程也较简单
直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 O(n)，而简单选择排序则与序列的初始状态无关
希尔排序作为插入排序的拓展，对较大规模的排序都可以达到很高的效率，但目前未得出其精确的渐近时间
堆排序利用了一种称为堆的数据结构，可在线性时间内完成建堆，且在 $O (n \log_{2} n)$ 内完成排序过程
快速排序基于分治的思想，虽然最坏情况下快速排序时间会达到 $O (n^{2})$ ，但快速排序平均性能可以达到 $O (n \log_{2} n)$ ，在实际应用中常常优于其他排序算法
归并排序基于分治的思想，由于其分割子序列与初始序列的排列无关，它的最好、最坏和平均时间复杂度均为 $O (n \log_{2} n)$

从空间复杂度看：

简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要借助常数个辅助空间
快速排序在空间上只使用辅助栈，用于实现递归，平均情况下大小为 $O (\log_{2} n)$ ，当然在最坏情况下可能会增长到 O(n)
2 路归并排序在合并操作中需要借助的辅助空间用于元素复制大小为 O(n)，虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加

从稳定性看：

插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法
简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法

从过程特征看：

采用不同的排序算法，在一次循环或几次循环后的排序结果可能是不同的

考研题中经常出现给出一个待排序的初始序列和已经部分排序的序列，问其采用何种排序算法

这就要对各类排序算法的过程特征十分熟悉，如冒泡排序和堆排序在每趟处理后都能产生当前的最大值或最小值，而快速排序一趟处理就能确定一个元素的最终位置等

考点追踪：总结对比各种算法的性能指标（2009、2010、2017、2020、2021、2022、2023、2025）

时空复杂度、稳定性。2. 比较/移动次数与初态的关系。3. 在已基本有序或接近逆序的情况下的算法选择建议。

究极对比：内部排序算法性能表 (2025 必备)

| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |

| :--- | :--- | :--- | :--- | :--- |

| 直接插入 | $O (n^{2})$ | $O (n^{2})$ | $O (1)$ | 稳定 |

| 冒泡排序 | $O (n^{2})$ | $O (n^{2})$ | $O (1)$ | 稳定 |

| 简单选择 | $O (n^{2})$ | $O (n^{2})$ | $O (1)$ | 不稳定 |

| 希尔排序 | $O (n^{1.3})$ | $O (n^{2})$ | $O (1)$ | 不稳定 |

| 快速排序 | $O (n \log n)$ | $O (n^{2})$ | $O (\log n)$ | 不稳定 |

| 堆排序 | $O (n \log n)$ | $O (n \log n)$ | $O (1)$ | 不稳定 |

| 归并排序 | $O (n \log n)$ | $O (n \log n)$ | $O (n)$ | 稳定 |

| 基数排序 | $O (d (n + r))$ | $O (d (n + r))$ | $O (r)$ | 稳定 |

内部排序算法的应用

选取排序方法需要考虑的因素：

待排序的元素数目 n
元素本身信息量的大小
关键字的结构及其分布情况
稳定性的要求
语言工具的条件，存储结构及辅助空间的大小等

排序算法小结：

若 n 较小，可采用直接插入排序或简单选择排序；因简单选择排序的的移动次数，当记录本身信息量较大时，用简单选择排序较好
若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜
若 n 较大，则应采用时间复杂度为 $O (n \log_{2} n)$ 的排序方法：快速排序、堆排序或归并排序
快速排序被认为是目前基于比较的内部排序方法中最好的方法
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况
若要求排序稳定则可选用归并排序，可以先利用直接插入排序求得较长的有序子文件，然后两两归并
在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的 n 个关键字随机分布时，任何借助于比较的排序算法，至少需要 $O (n \log_{2} n)$ 的时间
若 n 很大，记录的关键字位数较少且可以分解时，采用基数排序较好
当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构

外部排序

外部排序的基本概念

在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序

因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序

在排序过程中需要多次进行内存和外存之间的交换，这种排序方法就称为外部排序

外部排序的方法

排序的思路

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的

因为磁盘读/写的操作相对于内存运算来说较慢，因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即 I/O 次数

外部排序通常采用归并排序法，它包括两个相对独立的阶段：

把大文件分成多个子文件，把子文件加载进内存排序好再写回磁盘，称这些有序子文件为归并段或顺串
对这些归并段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件为止

例如一个含有 2000 个记录的文件，每个磁盘块可容纳 125 个记录，首先通过 8 次内部排序得到 8 个初始归并段 R1~R8，每个段都含有 250 个记录，然后对这些归并段继续归并，直到归并成一个文件，归并过程如下图

两个归并段的 2 路平衡归并的排序过程：

把内存工作区等分为 3 个缓冲区，其中的两个为输入缓冲区，一个为输出缓冲区
从两个输入归并段 R1 和 R2 中分别读入一个块，放在输入缓冲区 1 和输入缓冲区 2 中
在内存中进行2路归并，归并后的对象顺序存放在输出缓冲区中
若输出缓冲区中对象存满，则将其顺序写到输出归并段 R1' 中，再清空输出缓冲区，继续存放归并后的对象
若某个输入缓冲区中的对象取空，则从对应的输入归并段中再读取下一块，继续参加归并
如此继续，直到两个输入归并段中的对象全部读入内存并都归并完成为止

选择题：m 路平衡归并排序的过程中，需要设置 m 个输入缓冲区和 1 个输出缓冲区

考点追踪：外部排序、置换-选择与最佳归并树（2016、2019、2023）

利用置换-选择排序产生更长的初始归并段。2. 败者树减少了路数 $k$ 增大时的内部比较次数。3. 最佳归并树（Huffman 树应用）的构造及虚段数量补足： $(n_{0} - 1) % (k - 1) = u$ ，若 $u \neq 0$ ，则需补 $k - u - 1$ 个。

性能优化的思路

在外部排序中实现两两归并时，需要不停地将数据读出、写入磁盘，而这会耗费大量的时间

一般情况下：外部排序的总时间 = 内部排序所需的时间 + 外部存储读写的时间 + 内部归并所需的时间

内部排序是指，生成归并段；内部归并是指，把输入缓存区的数据归并到输出缓冲区；外部存储读写是指，把文件读入输入缓存区，把输出缓冲区写入文件

显然，外存信息读写的时间远大于内部排序和内部归并的时间，因此应着力减少 I/O 次数

每一趟归并需对文件读和写一遍，3 趟归并加上内部排序时所需进行的读/写，使得总共需进行 4 遍读写

若改用 4 路归并排序，则只需 2 趟归并，外部排序时的总读/写次数便减至 3 遍读写，依次可以通过增大归并数来减少 I/O

一般地，对 r 个初始归并段，做 k 路平衡归并，归并树可用严格 k 叉树（即只有度为 k 与度为 0 的结点的 k 叉树）来表示

第一趟可将 r 个初始归并段归并为 $⌈ r / k ⌉$ 个归并段，以后每趟归并将 m 个归并段归并成 $⌈ m / k ⌉$ 个归并段，直至最后形成一个大的归并段为止

树的高度 - 1 = $⌈ \log_{k} r ⌉$ = 归并趟数 S，可见，只要增大归并路数 k 或减少初始归并段个数 r 都能减少归并趟数 S，进而减少读写磁盘的次数，达到提高外部排序速度的目的

多路平衡归并与败者树

增加归并路数 k 时，内部归并的时间将增加，做内部归并时，在 k 个元素中选择关键字最小的记录需要比较 k - 1 次

每趟归并 n 个元素需要做 (n - 1)(k - 1) 次比较，S 趟归并总共需要的比较次数为 $S (n - 1) (k - 1)$ = $⌈ \log_{k} r ⌉ (n - 1) (k - 1)$ = $⌈ \log_{2} r ⌉ (n - 1) (k - 1) / ⌈ \log_{2} k ⌉$ 其中， $(k - 1) / ⌈ \log_{2} k ⌉$ 随 k 增长而增长，因此内部归并时间亦随 k 的增长而增长

这将抵消由于增大k而减少外存访问次数所得到的效益。因此，不能使用普通的内部归并排序算法

为了使内部归并不受 k 的增大的影响，引入了败者树：

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

因为 k 路归并的败者树深度为 $⌈ \log_{2} k ⌉$ ，因此 k 个记录中选择最小关键字，最多需要 $⌈ \log_{2} k ⌉$ 次比较

所以总的比较次数为 $S (n - 1) ⌈ \log_{2} k ⌉ = ⌈ \log_{k} r ⌉ (n - 1) ⌈ \log_{2} k ⌉ = (n - 1) ⌈ \log_{2} r ⌉$

使用败者树后，内部归并的比较次数与 k 无关了，只要内存空间允许，增大归并路数 k 将有效地减少归并树的高度，从而减少 IO 次数，提高外部排序的速度

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

每趟会读取和写入一次文件的内容，所以减少趟数会减少读写的内容
但是减少趟数需要增加归并路数，即增加输入缓冲区数量，这样会减少输入输出缓冲区的大小，从而增加读写的次数

置换-选择排序

置换-选择算法用来产生更长的初始归并段，从而减少初始归并段个数，来减少归并的时间

设初始待排文件为 FI，初始归并段输出文件为 FO，内存工作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 w 个记录

置换-选择算法的步骤如下：

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

核心结论：外部排序深度技巧 (2023、2025)

败者树：目的是在 $k$ 路归并时，使内部归并的选择次数从 $O (k - 1)$ 降低为 $O (\log_{2} k)$ ，从而使总时间与 $k$ 无关。

置换-选择排序：打破内存限制，生成初始归并段的长度平均可达 $2 \times$ 内存大小。

最佳归并树：利用 Huffman 树思想。虚段补足公式：若 $(n_{0} - 1) % (k - 1) = u \neq 0$ ，则需补 $k - u - 1$ 个空归并段。

读写次数：总 I/O = $2 \times (生成段读取 / 写回 + \sum 每趟读 / 写)$ 。归并趟数 $S = ⌈ \log_{k} r ⌉$ 。

核心技巧：最佳归并树的虚段补足

若初始归并段 $n_{0}$ ，归并路数 $k$ 。

计算 $u = (n_{0} - 1) (\mod k - 1)$ 。

若 $u = 0$ ，则不需要补虚段。

若 $u \neq 0$ ，则需补补充 $(k - 1) - u$ 个权值为 0 的虚段。

也可以使用 $n + e = k + d (k - 1)$ ，e 是添加的零的个数，d 是最小整数令 $k + d (k - 1) \geq n$ ，k 是归并的路数

归纳总结

直接插入排序、冒泡排序、简单选择排序它们主要用于元素个数 n 不是很大（n < 10000）的情形
它们的平均时间复杂度均为 $O (n^{2})$ ，实现也都非常简单
直接插入排序对于规模很小的元素序列（n ≤ 25）非常有效
冒泡排序和直接插入在最好情况下，只需要一趟排序过程就可以完成，只需要 n - 1 次比较操作且不需要交换操作
简单选择排序的关键字比较次数总是 $O (n^{2})$ ；最好情况下数据不需要移动，最坏情况下元素移动次数不超过 3(n - 1)
从空间复杂度来看，这三种基本的排序方法仅需要一个辅助元素
从稳定性来看，直接插入排序和冒泡排序都是稳定的；简单选择排序不是
对于中等规模的元素序列（n ≤1000 )，希尔排序是一种很好的选择
理论上和实验上已证明，希尔排序的比较次数和移动次数比直接插入排序时少得多，特别是当 n 越大时效果越明显
希尔排序代码简单，基本上不需要什么额外内存，但希尔排序是一种不稳定的排序算法
对于元素个数 n 很大的情况，可以采用快排、堆排序、归并排序、基数排序
其中快排和堆排序都是不稳定的，而归并排序和基数排序是稳定的排序算法
- 快速排序是最通用的高效内部排序算法，特别是它的划分思想经常在很多算法设计题中出现
- 平均情况下它的时间复杂度为 $O (n \log_{2} n)$ ，额外空间也是 $O (\log_{2} n)$
- 最坏情况时间复杂度会增加到 $O (n^{2})$ ，空间复杂度也会增加到 $O (n)$ ，但可以通过“三者取中”法来避免最坏情况的发生
堆排序也是一种高效的内部排序算法，它的时间复杂度是 $O (n \log_{2} n)$ ，而且不会的运行明显变慢，并且堆排序基本上不需要额外的空间。但堆排序不大可能提供比快速排序更好的平均性能
归并排序也是一个重要的高效排序算法，它的一个重要特性是性能与输入元素序列无关，时间复杂度总是 $O (n \log_{2} n)$ 。归并排序的主要缺点是需要 O(n) 的额外存储空间
- 基数排序是一种相对特殊的排序算法，它们对关键字的不同位部分进行处理和比较、
- 在常规编程环境中，基数排序的线性时间开销并不比快速排序的时间开销小很多，且其适应性远不如普通的进行比较和交换操作的排序方法
- 在实际工作中，常规的高效排序算法如快速排序的应用要比基数排序广泛得多
- 基数排序需要的额外存储空间包括待排序元素大小的空间及与基数数目相等的一系列桶
混合使用
我们可以混合使用不同的排序算法，如可以将直接插入排序集成到归并排序的算法中
这种混合算法能够充分发挥不同算法各自的优势，从而在整体上得到更好的性能

排序的基本概念 ​

插入排序 ​

直接插入排序 ​

折半插入排序 ​

希尔排序 ​

交换排序 ​

冒泡排序 ​

快速排序 ​

综合应用题 ​

奇偶分开 ​

第 k 位置元素 ​

荷兰国旗 ​

选择排序 ​

简单选择排序 ​

堆排序 ​

堆 ​

定义 ​

构建 ​

插入 ​

删除 ​

堆排序 ​

归并排序和基数排序 ​

归并排序 ​

基数排序 ​

各种内部排序算法的比较及应用 ​

内部排序算法的比较 ​

内部排序算法的应用 ​

外部排序 ​

外部排序的基本概念 ​

外部排序的方法 ​

排序的思路 ​

性能优化的思路 ​

多路平衡归并与败者树 ​

置换-选择排序 ​

归纳总结 ​

排序的基本概念

插入排序

直接插入排序

折半插入排序

希尔排序

交换排序

冒泡排序

快速排序

综合应用题

奇偶分开

第 k 位置元素

荷兰国旗

选择排序

简单选择排序

堆排序

堆

定义

构建

插入

删除

堆排序

归并排序和基数排序

归并排序

基数排序

各种内部排序算法的比较及应用

内部排序算法的比较

内部排序算法的应用

外部排序

外部排序的基本概念

外部排序的方法

排序的思路

性能优化的思路

多路平衡归并与败者树

置换-选择排序

归纳总结