首页/数据结构/第 8 章 排序
408 计算机学科专业基础 数据结构 第 8 章

排序
十种内部排序与外部排序

每年 2–3 道选择题,偶有综合题。必会:每种算法第一、二趟后的结果;复杂度与稳定性总表;堆的建立与调整;外部排序的归并趟数与最佳归并树。

记排序算法最有效的方法不是背表格,而是亲手跑几趟:本页每个算法都配了逐趟展示的模拟器,看懂过程后,复杂度和稳定性几乎都能自己推出来。

7 个考点模块 7 个排序模拟器 1 张图
左边已有序,橙色是本趟正在插入的元素
00
复习策略

考频地图

★★★★★ 核心章 选择 + 综合

排序每年 2–3 道选择题,偶有综合题。考法几乎都是:给出某种排序第几趟后的结果,或比较各算法的复杂度、稳定性、适用场景。下面每个算法都可以在模拟器里逐趟看结果。

考点考频常见问法
各算法的趟过程★★★★★“第一趟 / 第二趟后的序列是”
复杂度与稳定性★★★★★“下列排序中不稳定的是”“与初始序列无关的是”
快速排序★★★★★“第二趟后可能的结果”“最坏情况”
堆★★★★☆“建堆后的序列”“插入 / 删除后的比较次数”
外部排序★★★☆☆“归并趟数”“败者树”“最佳归并树虚段数”
一句话:稳定的排序记口诀“插冒归基”(直接插入、冒泡、归并、基数),其余(希尔、快排、选择、堆)不稳定。平均最快是快排,最坏也能 O(n log n) 的是堆排序和归并;每趟能让一个元素到达最终位置的是冒泡、选择、堆排序和快排(枢轴)。
01
8.1 · 高频

插入类排序

★★★★☆ 高频 选择题

直接插入:把第 i 个元素插入前面已排好的 i − 1 个元素中(从后往前比较、后移)。初始越有序越快,最好 O(n)。折半插入:用折半查找确定插入位置,比较次数降为 O(n log n),但移动次数不变,仍是 O(n²)。

希尔排序:先按增量 d 把序列分成若干子序列,各自直接插入排序;逐步缩小 d,最后 d = 1 再做一次整体插入排序。前面几趟让序列“基本有序”,最后一趟插入就很快。

  • 希尔排序的趟数和结果依赖于增量序列,题目会给出;d = 1 那趟就是直接插入。
  • 希尔排序不稳定(相同关键字可能被分到不同子序列),且只能用于顺序存储。
02
8.2 · 必考

交换类排序:冒泡与快排

★★★★★ 必考 选择 + 综合

冒泡:每趟从后往前(或从前往后)两两比较相邻元素,逆序就交换;每趟把一个最小(或最大)元素放到最终位置。某趟没有发生交换就说明已有序,可提前结束——所以最好 O(n)。

快速排序

选一个枢轴(通常是第一个元素),一趟“划分”把比它小的放左边、比它大的放右边,枢轴落在最终位置;再对左右两部分递归。

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(n²),递归栈深度 O(n)。改进:随机选枢轴或三数取中。
  • 平均 O(n log n),是所有内部排序中平均性能最好的。递归栈平均 O(log n)。
  • “第 k 趟后的结果”判断(2019 真题考法):每趟划分后枢轴到达最终位置。第二趟结束后,至少有 2 个元素在最终位置;若第一趟的枢轴不在端点(左右两边都要继续划分),则第二趟后至少有 3 个元素归位。
03
8.3 · 必考

选择类排序:简单选择与堆排序

★★★★★ 必考 选择 + 综合

简单选择:每趟在未排序部分选出最小的,与未排序部分第一个交换。比较次数恒为 n(n − 1)/2,与初始序列无关;不稳定(交换可能跨过相同关键字)。

堆排序

大根堆:完全二叉树中每个结点 ≥ 其孩子(L(i) ≥ L(2i),L(i) ≥ L(2i + 1))。排序过程:

  1. 建堆:从最后一个非叶结点 ⌊n/2⌋ 到 1,依次向下调整(与较大的孩子比较,小于它就交换并继续向下)。建堆时间 O(n)。
  2. 输出:堆顶(最大)与最后一个元素交换,堆大小减 1,对新堆顶向下调整(O(log n))。
  3. 重复 n − 1 次。总 O(n log n),空间 O(1),不稳定。

堆的插入与删除(2015 真题):小根堆 8, 15, 10, 21, 34, 16, 12,删除 8 后重建堆,比较几次?→ 把末尾 12 放到堆顶:先比较两个孩子 15 和 10(1 次),再拿较小的 10 和 12 比(2 次),交换;12 来到位置 3,只有一个孩子 16,比较一次(3 次),不交换。共 3 次。插入则放在末尾向上调整,每层只和父结点比较一次。

04
8.4 · 高频

归并、基数与计数排序

★★★★☆ 高频 选择题

二路归并:把相邻的两个有序子序列合并成一个,第一趟子序列长 1,第二趟长 2,……,共 ⌈log₂n⌉ 趟,每趟 O(n)。需要 O(n) 辅助空间,稳定。

基数排序(LSD):不比较关键字,按位“分配 + 收集”。从最低位开始,按该位的值把元素放入 r 个队列(桶),再按桶号顺序收集;做 d 趟(d 为位数)。必须用稳定的分配方式,否则高位排序会打乱低位结果。

计数排序:关键字是 0 ~ k 的整数时,先统计每个值出现的次数,再算出每个值的最终位置(前缀和),从后往前把元素放到输出数组(保证稳定)。时间、空间 O(n + k),k 很大时不适用。

05
8.5 · 必考

复杂度与稳定性总表

★★★★★ 必考 选择题
算法最好平均最坏空间稳定备注
直接插入O(n)O(n²)O(n²)O(1)✓基本有序时最快
折半插入O(n log n) 次比较O(n²)O(n²)O(1)✓只减少比较,移动不变
希尔—约 O(n^1.3)O(n²)O(1)✗只能用于顺序表
冒泡O(n)O(n²)O(n²)O(1)✓每趟一个元素归位
快速O(n log n)O(n log n)O(n²)O(log n) ~ O(n)✗平均最快;有序时最差
简单选择O(n²)O(n²)O(n²)O(1)✗比较次数与初始序列无关
堆排序O(n log n)O(n log n)O(n log n)O(1)✗建堆 O(n);适合选前 k 个
二路归并O(n log n)O(n log n)O(n log n)O(n)✓趟数 ⌈log₂n⌉;外部排序基础
基数(LSD)O(d(n + r))O(d(n + r))O(d(n + r))O(r)✓不基于比较;d 位、基数 r
计数排序O(n + k)O(n + k)O(n + k)O(n + k)✓关键字范围 k 较小时适用
问题答案
比较次数与初始序列无关简单选择(还有基数排序不比较)
趟数与初始序列有关冒泡(可提前结束)、快排
每趟至少一个元素到最终位置冒泡、简单选择、堆排序、快排(枢轴)
基本有序时最好的直接插入、冒泡(O(n))
从大量数据中选前 k 个堆排序(O(n log k))
链表上能用的直接插入、冒泡、简单选择、归并、基数(希尔、堆、折半插入不行)
基于比较的排序时间下界⌈log₂(n!)⌉ 次比较,即 Ω(n log n)
06
8.6 · 中频

外部排序

★★★☆☆ 中频 选择题

数据太大放不进内存时:① 分批读入内存排序,生成若干初始归并段写回磁盘;② 对归并段做多路归并。时间主要花在磁盘 I/O 上,所以要减少归并趟数。

r 个初始归并段做 k 路平衡归并,归并趟数 S = ⌈log_k r⌉ 减少趟数的两条路:增大 k(多路归并)、减少 r(让初始归并段更长)

一、败者树:让多路归并时选最小值更快

胜者 3 b1b0b2 10 9 20 6 归并段 0段 1段 2段 3 内部结点记录“败者”(较大者)胜者继续向上比较输出胜者后,只需沿它的路径重新比较 ⌈log₂k⌉ 次
图 8-1 败者树:k 路归并中每选出一个最小元素只需 ⌈log₂k⌉ 次比较(普通方法要 k − 1 次),使总比较次数与 k 无关。

二、置换-选择排序:生成更长的初始归并段

用一个大小为 w 的工作区:每次输出工作区中“不小于上一个输出值”的最小者,再读入一个新记录;工作区里全是比上一个输出值小的记录时,当前归并段结束,开始下一段。得到的初始归并段平均长度约为 2w,且长度不等。

三、最佳归并树:长度不等的归并段怎么合并 I/O 最少

把每个归并段的长度(块数)当作权值,构造 k 叉哈夫曼树,WPL × 2 就是总读写次数。若 (n₀ − 1) % (k − 1) = u ≠ 0,需要补 k − 1 − u 个长度为 0 的虚段。例:8 个归并段做 3 路归并,(8 − 1) % 2 = 1,补 2 − 1 = 1 个虚段。

07
实战

真题与自测

★★★★★ 收口 选择 + 综合

一、真题问法

问法 1:“对 {46, 79, 56, 38, 40, 84} 用快速排序(以第一个元素为枢轴),第一次划分后的结果是?”→ 40, 38, 46, 56, 79, 84。

问法 2(2015 真题):“小根堆 8, 15, 10, 21, 34, 16, 12,删除 8 后重建堆的比较次数?”→ 3 次。

问法 3:“下列排序算法中,元素的移动次数和关键字的初始排列次序无关的是:直接插入、冒泡、基数、快速?”→ 基数排序。

问法 4:“对 10 TB 的数据文件排序,应使用的方法是?”→ 外部排序(归并排序)。

二、折叠自测

1. 稳定的排序有哪些?

直接插入、折半插入、冒泡、归并、基数、计数。

2. 快速排序什么时候最慢?

初始序列有序或逆序(枢轴总是最大或最小),O(n²)。

3. 建堆的时间复杂度?

O(n)。

4. 二路归并排序 n = 1000 需要几趟?

⌈log₂1000⌉ = 10 趟。

5. 100 个初始归并段做 4 路归并要几趟?

⌈log₄100⌉ = 4 趟。

6. 5 个元素排序至少需要几次比较(最坏情况下)?

⌈log₂(5!)⌉ = ⌈log₂120⌉ = 7 次。

三、考前速览

3 句话

稳定:插冒归基。
平均最快:快排;最坏也 O(n log n):堆、归并。
归并趟数 ⌈log_k r⌉。

3 个易错

① 简单选择比较次数与初始序列无关。
② 希尔、堆排序不能用于链表。
③ 快排有序时最慢,插入有序时最快。