第七章排序 — 速览

数据结构目录阅读详版下载 Markdown

一、排序概念

有序表查找远快于无序表（如二分查找 $O(\log_2 n)$ ），故排序是常见数据操作。

关键字：取数据记录中某一字段值作为比较依据，称关键字；下文数据值特指关键字值。

稳定排序：设 $R_i$ 、 $R_j$ 关键字值相同且排序前 $R_i$ 在 $R_j$ 之前，排序后仍保持 $R_i$ 在 $R_j$ 之前，则为稳定排序；否则为不稳定排序。

内排序：数据可一次性全部载入内存，只与内存打交道。外排序：数据不能一次全部载入内存，过程中需内外存之间数据交换。

基础操作：比较和交换是基础；比较以 >、>=、<、<=、== 二元操作为基础。如无特殊说明，排序后假定为非递减序列。

二、内排序

对比表

算法	核心思想	最好	最坏	平均/一般	稳定性	关键易错点
冒泡排序	相邻两两比较，大者后移，每趟把最大元素冒泡到尾部	$O(n)$	$O(n^2)$	$O(n^2)$	稳定	内层比 a[i] 与 a[i+1]，左界 $i=0$ 、右界 $i=n-2$ ；外层 $j$ 从 $n-1$ 递减到 1；无交换标志可提前结束
插入排序	将元素逐个插入到前面有序序列的适当位置	$O(n)$	$O(n^2)$	$O(n^2)$	稳定	从后往前扫描，遇 `a[i]<=x` 停（break），否则后移；最后在 `a[i+1]` 写入 x
希尔排序	先按步长分组做插入排序预处理使序列比较有序，最后 step=1 再插入	—	—	外中两重循环已达 $n\log_2 n$ （预处理不再细分析）	不稳定	step 从 $n/2$ 起逐次减半到 1，整数除法下约 $\lfloor\log_2 n\rfloor$ 个值；相等元素可能分到不同子序列致次序改变
归并排序	把每个元素看作长 1 有序段，两两归并直到长 n	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n\log_2 n)$	稳定	取等用 `a[i]<=a[j]` 让前序列先入结果（稳定性依据）；一方越界则抄完另一方剩余
快速排序	选标杆 pivot，小者前、大于等于者后，递归处理左右子序列	$O(n\log_2 n)$	$O(n^2)$	介于其间	不稳定	首洞位置与首次搜索方向必须配套（首洞最左则先从右向左搜）；标杆元素需先换到首位
选择排序	从左到右，为每个位置在剩余区间选最小值换过来	$O(n^2)$	$O(n^2)$	$O(n^2)$	不稳定	内层 `j=i+1` 起，维护 minIndex，整趟扫完才交换一次；`minIndex==i` 时跳过交换
堆排序	建大顶堆，摘堆顶换到尾部，重新调整，循环至有序	—	$O(n\log_2 n)$	$O(n\log_2 n)$	不稳定	建堆从倒数第一个非叶子结点 $(n-1)/2$ 起向前；建堆可紧分析为 $O(n)$ ，摘取阶段为 $O(n\log_2 n)$
基数排序	把单一关键字各位视作多关键字，按位分配收集（LSD 低位优先）	—	—	$O(mn)$ （ $m$ 为最大值位数）	稳定	口袋数取决于每位取值范围（十进制 10 个），与 $n$ 无关；采用 LSD 而非 MSD

各算法极简补充

冒泡排序：第一趟两两比较把最大元素换到第 $n$ 位，再在前 $n-1$ 个中重复；某趟无交换即已有序可提前结束。共比较 $n(n-1)/2$ 次。

插入排序：第 1 个元素自成有序序列，逐个把后续元素插入；正序时仅比较不移动达 $O(n)$ ，逆序时比较与移动均为 $\dfrac{n(n-1)}{2}$ 。

希尔排序：下标间隔为 step 的元素归入同一子序列；不稳定反例 80, 30(a), 30(b), 50 排序后 30(b), 30(a), 50, 80，相等 30 次序被颠倒。

归并排序：两路归并设两序列用 $i$ 、 $j$ 扫描、结果用 $k$ ，每步取较小者，仅取走一侧指针前移；一方越界则抄完另一方。结果长 $n+m$ ，归并处理量为 $O(n+m)$ ，关键字比较次数在两序列均非空时至多为 $n+m-1$ ；按 $n$ 为 2 的幂分析，时间递推 $t(n)=2t(n/2)+n=2^k t(1)+kn$ ， $k=\log_2 n$ 。

快速排序：采用"挖洞"法，左右指针交替向中间逼近、洞在两侧搬移元素，相遇即标杆归位，再递归处理左右。一趟代价 $O(n)$ ；标杆落中间为最好 $\log_2 n$ 趟，完全逆序/正序为最坏 $O(n^2)$ 。优化：取中间位置值为标杆，或首尾中三者取中值。

快速排序不稳定反例：对 80, 72(a), 72(b) 取 temp=80，从右向左先把 72(b) 移入洞，结果 72(b), 72(a), 80，相等 72 次序由 (a)(b) 变 (b)(a)。

选择排序：在 $[0,n-1]$ 找最小换到 0 位，在 $[1,n-1]$ 找最小换到 1 位……共比较 $\dfrac{n(n-1)}{2}$ 次。不稳定源于跨不相邻位置的交换；反例 72(a),72(b),8 排序后 8,72(b),72(a)。

堆排序：大顶堆为完全二叉树中任一结点值不小于其左右子；建堆从后往前逐个调整非叶子结点，摘堆顶与末元素交换并缩小规模重新调整。调整 adjust 中左子下标 2*i+1，左右子取较大者；相等时右子优先，故父与较小孩子值相同时可能反转（不稳定）。反例 5(a),80,5(b) 排序后 5(b),5(a),80。

堆排序复杂度：建堆总调整次数 $t=\sum_{i=h-1}^{0}2^{i}(h-i)=n-(h+1)$ ， $h$ 为对数阶，故建堆 $O(n)$ ；摘取阶段规模递减，时间 $O(n\log n)$ 。

基数排序：多关键字有主次之分，先按主关键字、相同再按次关键字。MSD 先高位、需 $m$ 层逐层分裂子子序列较复杂；LSD 先低位、按位分配到 10 个口袋再统一收集、只需 $m$ 趟，更便捷，基数排序采用 LSD（口袋排序法）。每趟分配 $O(n)$ 、收集为常量 10、回写 $O(n)$ ，共 $m$ 趟得 $O(mn)$ 。

优先队列（堆的应用）

约定级别值小者优先级高，用小顶堆、堆顶为优先级最高元素。线性结构进/出队总有一个 $O(1)$ 、另一个 $O(n)$ ；改用小顶堆使进、出队均降到树高 $O(\log_2 n)$ 。

出队：读堆顶 $O(1)$ ，把尾元素填到堆顶再向下 adjust 下沉恢复堆序，总 $O(\log_2 n)$ 。进队：新元素加到尾部成叶子，向上与父比较、小则交换上浮，直到不小于父或到根， $O(\log_2 n)$ 。两者调整方向相反。

牛刀小试判断要点

例题一（四种算法中最差时间复杂度为 $O(n\log n)$ 的个数）：幻灯片标注答案为 A，即 1 个；判断时逐一比对直接选择、堆、快速、基数排序的最差时间复杂度是否等于 $O(n\log n)$ 。

例题二（百万乱序整数选最小 $k=100$ 个、最快算法）：幻灯片标注答案为 D，即堆排序；题目允许完成任务后提前退出，应选支持提前终止、只需局部完成即可取得最小 $k$ 个的算法。

例题三（满足稳定性的二分插入排序）：二分查找插入位置时用 <=（而非 <）比较，相等时 low=mid+1 把区间推向右侧，使插入位置位于已有相等关键字元素之后，从而保持稳定。

三、外排序

定义与瓶颈：数据太多无法一次载入内存，需多次内外存数据交换；外存访问远慢于内存，时间耗费主要在外存读写上，核心是减少外存读写次数。

基本思路（两阶段）：预处理阶段把 $N$ 个记录分批读入内存、用内排序形成有序片段（初始归并段）；归并阶段把这些片段归并为一个有序文件。

设备：磁带为顺序存取，有效排序至少需两个磁带机、三个可简化问题；磁盘为随机存取（柱面–盘片–磁道–扇区–页面）。归并排序每次只需访问序列第一元素，契合磁带顺序文件。

预处理规律：每次读入记录数越小，初始片段越多；片段越多，归并次数越多。

二路/K 路归并：二路归并将两有序序列归并为一，外排序需 4 条磁带（A1、A2、B1、B2），逐趟源目标互换、片段变长数变少；有 $2K$ 个磁带即可实现 $K$ 路归并。

多阶段归并：只有 $k+1$ 个磁带也可做 $k$ 路归并，比 K 路归并所需 $2K$ 条磁带更省。设 A、B1…Bk，每次将 B1…Bk 的 $k$ 个有序序列归并到 A，某磁带空后又成 $k$ 满一空，循环至只剩一条磁带有数据。

斐波那契分布：把片段平均分配（如 17/17）看似直观，却一趟后无法直接继续，应不均匀分布。若片段数为斐波那契数 $F_N$ ，最佳分布为 $F_N=F_{N-1}+F_{N-2}$ （如 $34=21+13$ ）；若不是斐波那契数，需填充长度为 0 的虚拟片段凑成斐波那契数。

置换选择：动机是拉长初始归并段长度以减少段数 $m$ （ $k$ 路归并趟数约 $\log_k m$ ）。在仅容 $p$ 个记录的内存中可生成平均长度 $2p$ 的片段。每步输出内存最小值、空位立即补读一个新元素；新元素若不小于本片段已输出最大值则并入当前段，否则留到下一段；当前段无可加入元素时开启下一段。选最小值朴素逐比为 $O(p)$ ，用最小化堆降为 $O(\log_2 p)$ 。

置换选择示例：序列 $3,8,5,6,2,0,9,4,1,-5$ 、内存容量 3，生成片段 $3,5,6,8,9$ （长 5）/ $0,1,2,4$ / $-5$ ，验证片段可超过内存容量。

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

四、速记要点

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

不稳定排序：快速、希尔、选择、堆。

最坏 $O(n^2)$ ：冒泡、插入、选择、快速。

正序时可达 $O(n)$ ：冒泡、插入。

基数排序： $O(mn)$ ，当最大位数 $m$ 视为常数时可看作 $O(n)$ 。

可达 $O(n\log_2 n)$ ：归并排序、堆排序最坏情况、快速排序最好情况。

外排序口诀：预处理分段内排成初始归并段 + 归并；置换选择拉长片段减少段数； $k$ 路归并可用 $2k$ 个磁带，或仅用 $k+1$ 个磁带（多阶段归并）。

第七章 排序 — 速览