首页/考点精讲/数据结构 · 排序
考点精讲数据结构大纲 · 排序

排序
会手推一趟,会背一张表

选择 3–4 道几乎必有:给一趟结果问是哪种排序、复杂度与稳定性、某种初始序列下谁最快;应用题考外部排序(败者树、置换-选择、最佳归并树),算法题常借用快排划分或归并。

十种内部排序按“怎么让元素归位”分成五家:插入类(抓一张牌插进手里排好的牌)、交换类(逆序就换)、选择类(每趟挑最小的)、归并(两堆有序的合成一堆)、基数(不比较,按位分配收集)。

12 个大纲条目 1 张必背总表 1 处仅做理解
00
先看范围

大纲对照

★★★★★ 必考选择 + 应用
  1. 一排序的基本概念→ 01
  2. 二直接插入排序→ 01
  3. 三折半插入排序→ 01
  4. 四起泡排序(bubble sort)→ 02
  5. 五简单选择排序→ 03
  6. 六希尔排序(shell sort)→ 01
  7. 七快速排序→ 02
  8. 八堆排序→ 03
  9. 九二路归并排序(merge sort)→ 04
  10. 十基数排序→ 04
  11. 十一外部排序→ 06
  12. 十二排序算法的分析和应用→ 05
本页标为“仅做理解”的内容

计数排序、桶排序等其他线性时间排序。

不稳定的四个:快(快排)、些(希尔)、选(简单选择)、堆(堆排序),其余都稳定。每趟能确定一个元素最终位置的:冒泡、简单选择、快排(枢轴)、堆排序。
01
大纲 一、二、三、六

基本概念与插入类排序

★★★★☆选择

一、基本概念

  • 稳定性:关键字相同的两个元素,排序后相对次序不变就是稳定。它只是性质,不代表好坏。
  • 成绩单先按学号排好,再按总分排序。如果排序算法稳定,同分的同学仍然按学号从小到大排列;不稳定的话,同分同学的先后就乱了。所以“多关键字排序”(先按次要关键字、再按主要关键字)要求后一趟必须稳定。
  • 内部排序:全部数据在内存;外部排序:数据太多,要在内存和外存之间来回搬。
  • 基于比较的排序,最坏情况下至少要 ⌈log2(n!)⌉ 次比较,即下界 O(n log n)。

二、直接插入排序

像摸扑克牌:左边是已排好的,每次从右边拿一张,从后往前找位置插进去(比它大的依次后移)。
已排好的部分(手里的牌)本趟插入的元素
插入 13 时,前面 5 个元素都比它大,全部后移一位——这就是逆序时 O(n²) 的来源。注意“已排好的部分”只是相对有序,不是最终位置(13 插进来后,38 就往后挪了)。
打牌时摸一张、插一张:左手的牌始终是排好的,右手摸到新牌就从右往左比,找到位置插进去。
  • 最好(已有序)O(n):每趟只比 1 次不移动;最坏(逆序)O(n²);空间 O(1);稳定。
  • 适合基本有序或 n 较小的情况;顺序表、链表都可以用。
动手试一试:直接插入排序逐趟结果(可改成希尔、冒泡等其他算法)

三、折半插入排序

找插入位置用折半查找,只减少了比较次数(约 O(n log n)),移动次数不变,所以时间仍是 O(n²);稳定;只能用于顺序表。比较次数与初始序列无关。

四、希尔排序

插入排序在“基本有序”时很快。希尔排序先把间隔为 d 的元素分成一组各自插入排序,让整体先“大致有序”,再逐步缩小 d,最后 d = 1 做一次直接插入排序。
d = 5 时,下标相差 5 的元素为一组:(49,13)(38,27)(65,49*)(97,55)(76,04),各组内部插入排序(第一组用橙色标出)。几趟下来序列越来越“接近有序”,最后 d = 1 的直接插入排序几乎不用移动。
原来 49 在 49* 前面,排序后 49* 跑到了 49 前面——希尔排序不稳定的实例。
  • 时间依赖增量序列,约 O(n1.3),最坏 O(n²);空间 O(1);不稳定(相同关键字可能分在不同组);只能用于顺序表。
02
大纲 四、七

交换类:冒泡排序与快速排序

★★★★★选择 + 算法

一、冒泡排序

从后往前(或从前往后)两两比较,逆序就交换。一趟下来,最小(或最大)的元素“冒”到了最终位置。某一趟没发生交换,说明已经有序,可以提前结束。
从后往前两两比较:第 1 趟把最小的 13 一路换到最前面,第 2 趟把 27 换到第 2 位……第 4 趟一次交换都没有,说明已经有序,提前结束(不必做满 6 趟)。
  • 最好 O(n)(有序,1 趟 n − 1 次比较、0 次交换);最坏/平均 O(n²);空间 O(1);稳定(相等时不交换)。
  • 每趟确定一个元素的最终位置。

二、快速排序(最常考)

选一个枢轴(通常是第一个元素),一趟“划分”把比它小的都放左边、比它大的都放右边,枢轴落到最终位置;再对左右两部分递归。像整理书架:先挑一本做标尺,矮的放左、高的放右。
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; }

对 49 38 65 97 76 13 27 49' 以第一个元素为枢轴做一次划分。

high 从右往左找比 49 小的 → 27 填到位置 0;low 从左往右找比 49 大的 → 65 填到位置 6;high 继续找到 13 填到位置 2;low 找到 97 填到位置 5;high 左移与 low 相遇于位置 3,放入 49。
结果:27 38 13 49 76 97 65 49'。
虚线格子是“坑”。high 从右往左找小于枢轴的,low 从左往右找大于枢轴的,交替填坑;两指针相遇处就是枢轴的最终位置。
递归树的高度 = 递归深度 = 栈空间。左图每次大致对半分,深度约 log₂n;右图每次只分出一个元素,深度为 n,比较次数 n(n − 1)/2,这就是快排最坏 O(n²) 的样子。
动手试一试:快速排序逐趟结果
  • 时间:每次划分都均匀时 O(n log n);初始有序或逆序时最坏 O(n²)(每次只划出一个元素)。平均 O(n log n),是内部排序中平均性能最好的。
  • 空间:递归栈,最好 O(log n),最坏 O(n)。不稳定。
  • 判断“第几趟后的结果”:第 i 趟结束时,至少有 i 个元素处于最终位置(枢轴左边都比它小、右边都比它大)。第 2 趟若第一次的枢轴在边界上,只多 1 个;否则左右两边各多 1 个。
  • 快排的递归次数与划分是否均匀有关,与“先处理左还是右”无关;先处理较短的子区间可把栈深度控制在 O(log n)。
  • 算法题常用划分思想:找第 k 小的元素(平均 O(n))、把负数移到正数前面、荷兰国旗问题。
03
大纲 五、八

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

★★★★★选择 + 应用

一、简单选择排序

第 i 趟在后面 n − i + 1 个元素里挑最小的,和第 i 个交换。
每趟在未排序部分里挑最小的(不管序列原来是否有序,都要全部看一遍),和未排序部分的第一个交换。橙色是被换到后面去的元素——这种“远距离交换”正是不稳定的原因。
体育课按身高排队:老师每次从还没站好的同学里找最矮的,让他和当前位置的同学换位置。
  • 比较次数恒为 n(n − 1)/2,与初始序列无关;移动次数最多 3(n − 1)。时间 O(n²),空间 O(1)。
  • 不稳定:例 2 2' 1,第一趟 1 与 2 交换 → 1 2' 2。

二、堆排序

先把数组建成大根堆(堆顶最大)。然后反复:堆顶和最后一个元素交换(最大值归位到末尾),堆规模减 1,对新堆顶做下沉。n − 1 次后完成升序排序。建堆和下沉的细节见 DS·5 堆。
建堆 O(n) + (n − 1) 次下沉 × O(log n) = O(n log n) 最好、平均、最坏都是 O(n log n);空间 O(1);不稳定 升序用大根堆,降序用小根堆

大根堆 87 45 78 32 17 65 53 09,进行第一趟排序(输出堆顶并调整)后的序列?

87 与 09 交换 → 09 45 78 32 17 65 53 | 87;09 下沉:与较大孩子 78 交换,再与 65 交换 → 78 45 65 32 17 09 53 | 87。
每一趟:最大值换到数组末尾“归位”(绿色),堆缩小 1,新堆顶下沉。重复 n − 1 趟,数组就从小到大排好了。
动手试一试:堆排序逐趟结果
  • 只需要选出前 k 个最大(最小)值时,堆排序(或其思想)最合适:O(n + k log n)。
  • 堆排序适合 n 很大的情况;但元素少时建堆开销不划算。
04
大纲 九、十

二路归并排序与基数排序

★★★★☆选择

一、二路归并排序

把 n 个元素看成 n 个长度为 1 的有序段,两两合并成长度为 2 的有序段,再两两合并……直到只剩一段。合并两个有序表:两个指针比较,谁小先放谁。
竖线分隔各个有序段,每趟两两合并,段数减半,共 ⌈log₂7⌉ = 3 趟。合并两段时 i、j 各指一段的开头,谁小先放谁,放完的指针后移——需要一个同样大小的辅助数组,所以空间 O(n)。
  • 时间恒为 O(n log n)(与初始序列无关);空间 O(n)(辅助数组);稳定。
  • k 路归并:趟数 ⌈logk n⌉——外部排序的基础。

二、基数排序

不比较大小。按个位、十位、百位……(最低位优先 LSD)依次做“分配(按这一位放进 0–9 号桶)+ 收集(按桶号顺序串起来)”。每一趟都必须稳定,所以前面按低位排的结果在高位相同时得以保留。

278 109 063 930 589 184 505 269 008 083 按个位进行第一趟分配收集。

0 号:930;3 号:063、083;4 号:184;5 号:505;8 号:278、008;9 号:109、589、269。
收集:930 063 083 184 505 278 008 109 589 269。
第 1 趟:按个位分配
每趟收集后的序列
个位、十位、百位各做一趟“分配 + 收集”,3 趟后有序,全程没有比较过两个数的大小。第 2 趟十位都是 0 的 505、008、109 按第 1 趟的先后进 0 号桶——每趟稳定,低位的顺序才能保留下来。
整理一副扑克牌:先按点数分成 13 堆再收起来,然后按花色分成 4 堆再收起来,牌就按“花色 + 点数”排好了。按“年、月、日”排日期也可以用同样的办法(先日、再月、最后年)。
动手试一试:基数排序每趟收集结果
d 位关键字,基数 r(十进制 r = 10),n 个元素: 时间 O(d(n + r)),空间 O(r)(r 个队列),稳定
  • 基数排序适合关键字位数少、n 很大的情况,例如对 10000 个 0–999 的整数排序。

计数排序、桶排序

计数排序:统计每个值出现的次数,再按次数直接输出,O(n + k),适合值域 k 不大的整数。桶排序:按值域划分桶,桶内再排序。都是非比较排序,大纲未列。

05
大纲 十二

排序算法的分析和应用:必背总表

★★★★★ 必考选择
算法最好平均最坏空间稳定每趟定一个终位
直接插入O(n)O(n²)O(n²)O(1)✔✘
折半插入O(n log n)O(n²)O(n²)O(1)✔✘
希尔约 O(n1.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(1)✘✔
堆O(n log n)O(n log n)O(n log n)O(1)✘✔
二路归并O(n log n)O(n log n)O(n log n)O(n)✔✘
基数O(d(n + r))O(r)✔✘

怎么选(应用题思路)

  • n 小(≤ 50):直接插入或简单选择;记录本身很大(移动代价高)时选简单选择(移动少)。
  • 基本有序:直接插入、冒泡(O(n));别用快排(退化成 O(n²))。
  • n 大:快排(平均最快)、堆排序(空间 O(1)、最坏也 O(n log n))、归并(要求稳定时选它)。
  • n 很大、关键字位数少:基数排序。
  • 链表上排序:直接插入、冒泡、简单选择、归并、基数都行;希尔、折半插入、堆排序、快排(一般实现)依赖随机访问。
与初始序列的关系算法
比较次数与初始序列无关简单选择、折半插入、基数(不比较)、二路归并(次数有小幅差异,量级不变)
排序趟数与初始序列无关直接插入(n − 1 趟)、简单选择、基数、归并
趟数与初始序列有关冒泡(可提前结束)、快排(递归深度)
最常见的题:“下列序列是某排序算法第二趟后的结果,可能是哪种?”——检查哪些元素已在最终位置(冒泡/选择看两端;快排看是否存在“左边都小、右边都大”的元素;插入排序看前 3 个是否有序)。
06
大纲 十一

外部排序

★★★★☆选择 + 应用
100 GB 的文件,内存只有 1 GB,怎么排?两步:① 每次读入内存能装下的一部分,内部排好,写回磁盘,得到若干个有序的归并段;② 用多路归并把这些段合成一个。时间主要花在磁盘 I/O 上,所以一切优化都是为了减少归并趟数。
r 个初始归并段,k 路平衡归并: 归并趟数 S = ⌈log_k r⌉ 每一趟都要把全部数据读一遍、写一遍 → 减少 S 的两条路:增大 k(败者树)、减少 r(置换-选择排序)

一、败者树:让 k 增大时比较不变慢

  • k 路归并时每次要从 k 个段头中选最小的。普通方法要比较 k − 1 次,k 一大内部比较就变多,抵消了趟数减少的好处。
  • 败者树:一棵完全二叉树,叶子是 k 个段的当前元素,内部结点记录“比赛的败者”,胜者继续向上比,根上面再放总冠军。每选出一个最小值后,只需沿着该叶子到根的路径重赛:比较 ⌈log2k⌉ 次。
  • 使用败者树后,总比较次数与 k 无关,k 可以放心增大(但受内存缓冲区数量限制)。
4 路归并的败者树。叶子 b0~b3 是 4 个归并段当前的第一个元素。b0(10) 与 b1(9) 比,9 胜、10 是败者记在结点里;b2(20) 与 b3(6) 比,6 胜;两个胜者 9 与 6 再比,6 是冠军被输出。
输出 6 后,b3 段的下一个元素补进来,只需沿 b3 → 根这一条路重赛 ⌈log₂4⌉ = 2 次。
体育比赛的淘汰赛对阵图:每场比赛只记下“谁输了”,赢的人继续往上打。冠军被“取走”后,只需要让替补选手沿着原冠军那条路重新比几场,其他场次的结果都不用重打。

二、置换-选择排序:让初始归并段更长(r 更小)

内存工作区只能装 w 个记录,普通做法每段长度就是 w。置换-选择排序“边输出边读入”:每次输出工作区里不小于上一个输出值的最小记录,再读入一个新记录补位;小于上一个输出值的新记录只能等下一段。平均段长约 2w,且各段长度不等。

工作区 w = 3,输入 17 21 05 44 10 12 56 32 29,求初始归并段。

工作区 {17, 21, 05} 输出 05 读入 44 → 输出 17 读入 10 → 10 < 17 本段不能输出;输出 21 读入 12 → 输出 44 读入 56 → 输出 56 读入 32 → 剩下 {10, 12, 32} 都小于 56,第 1 段结束:05 17 21 44 56。
第 2 段:输出 10 读入 29 → 输出 12 → 输出 29 → 输出 32:10 12 29 32。
每行是输出并补入一个记录后的工作区。虚线灰格是比“上一个输出值”还小的记录,本段已经放不进去,只能“冻结”等下一段;当工作区全部冻结,本段结束。工作区只有 3 个位置,却得到了长度为 5 的段。

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

置换-选择产生的段长度不一样。每个段被读写的次数 = 它在归并树中的层数,所以这就是一个 k 叉哈夫曼树问题:段越长越晚合并。
若 (r − 1) mod (k − 1) ≠ 0,补 (k − 1) − (r − 1) mod (k − 1) 个长度为 0 的虚段 读写次数 = 2 × WPL(每个记录读一次写一次)

8 个初始段长度 2 3 6 9 12 17 18 24,做 3 路最佳归并,求 I/O 次数(每个记录读写各计 1 次)。

(8 − 1) mod 2 = 1 ≠ 0 → 补 1 个虚段 0。
{0, 2, 3} → 5;{5, 6, 9} → 20;{12, 17, 18} → 47;{20, 24, 47} → 91。
WPL = 5 + 20 + 47 + 91 = 163 → I/O = 2 × 163 = 326。
3 路最佳归并树:绿色叶子是 8 个初始段,虚线 0 是补上的虚段,内部结点是每次归并产生的新段。长度 2、3 的短段在第 3 层(被读写 3 遍),最长的 24 在第 1 层(只读写 1 遍)。
对一个 100 GB 的日志文件按时间排序,而内存只有 8 GB:先每次读 8 GB 排好写回(得到约 13 个有序段),再多路归并。整个过程的瓶颈是磁盘读写的遍数,所以要尽量减少归并趟数。
  • 败者树减少的是内部比较次数;置换-选择减少的是初始段数 r;最佳归并树减少的是段长不等时的总 I/O。别混。
  • k 路归并需要 k 个输入缓冲区 + 1 个输出缓冲区(考虑并行时还要加倍)。
07
收口

自测与考前速览

★★★★★自测
1. 数据基本有序时,哪种排序最快?哪种最慢?

直接插入(和冒泡)接近 O(n) 最快;快速排序退化为 O(n²) 最慢。

2. 要求稳定且 O(n log n),选哪个?

二路归并排序。

3. 空间 O(1) 且最坏 O(n log n),选哪个?

堆排序。

4. 序列 68 11 18 69 23 93 73 可能是升序快排第二趟后的结果吗?

不可能。排好后应为 11 18 23 68 69 73 93,对照发现没有任何元素处在最终位置;而快排第二趟后至少有 2 个元素已归位。

5. 败者树中 k = 8,每选出一个记录需比较几次?

⌈log28⌉ = 3 次。

6. 120 个初始段做 5 路平衡归并,需要几趟?

⌈log5120⌉ = 3 趟(5² = 25 < 120 ≤ 125 = 5³)。

7. 简单选择排序的比较次数与初始序列有关吗?

无关,恒为 n(n − 1)/2。

五句话

不稳定:快些选堆。
每趟定终位:冒泡、选择、快排、堆。
快排平均最快,有序时最坏 O(n²)。
归并 O(n) 空间换稳定;基数 O(d(n+r))。
外排:败者树增 k,置换-选择减 r,哈夫曼省 I/O。

五个易错

① 折半插入只减比较不减移动。
② 建堆 O(n),堆排序 O(n log n)。
③ 快排空间不是 O(1)。
④ 直接插入的有序部分不是最终位置。
⑤ 最佳归并树要先补虚段。