# 第七章 排序 — 速览 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/data-structures/chapter-07-quick/ ## 一、排序概念 有序表查找远快于无序表（如二分查找 $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$ 个磁带（多阶段归并）。