排序的定义与基本概念

2026 大纲 七（一）排序的基本概念。整章的公共地基：后面十一条目反复用到的术语全在这里定义一次。

排序的对象是记录，比较的依据是关键字

设含 $n$ 个记录的序列为 $\{R_1,\dots ,R_n\}$，关键字序列为 $\{K_1,\dots ,K_n\}$。排序就是确定 $1,2,\dots ,n$ 的一个排列 $p_1,\dots ,p_n$，使得

$$K_{p_1}\le K_{p_2}\le \cdots \le K_{p_n}$$

定义里有两处值得停一停，它们各自牵出后面一大片内容。

第一，排序的对象是"记录"，比较的依据只是它的"关键字"。 一条记录通常还带着关键字之外的数据项——学号是关键字，姓名、成绩是别的字段。正因为记录里有关键字之外的东西，交换两条记录的代价才可能远大于比较两个关键字。这就是本章为什么要把"比较次数"和"移动次数"分开统计，也是"记录很大时宁可多比较少移动"这类选型判断的来源。

第二，排序结果不一定唯一。 关键字全不相同时，满足上式的排列 $p$ 只有一个；只有存在两个以上关键字相等的记录时，合法排列才不止一个——稳定性这个概念也才有意义。

⚠️ 由此得到一条做题时的直接推论：关键字互不相同的例子，永远看不出算法稳不稳定。要举稳定性的反例，序列里必须先有一对相等的关键字。

稳定性：一个比较符号的直接后果

定义：设 $K_i=K_j$（$i\ne j$），排序前 $R_i$ 领先于 $R_j$。若排序后 $R_i$ 仍领先于 $R_j$，该方法稳定；若可能使 $R_j$ 领先于 $R_i$，则不稳定。

排序前:  3a  1  3b  2     （3a 与 3b 关键字相同，3a 在 3b 前面）
稳定:    1  2  3a  3b     （3a 仍在 3b 前面 ✓）
不稳定:  1  2  3b  3a     （3a 跑到 3b 后面 ✗）

🔴 判定是不对称的。 证不稳定只需举出一个具体输入推到底，指出某两个相等元素被颠倒——因为定义写的是"可能"。证稳定却要覆盖所有输入，举再多"这次没乱"都不算证明。

所以本章每篇讲到"不稳定"时都会给出具体反例序列：快排 {3a, 3b, 2}、简单选择 {2a, 2b, 1}、希尔 {2a, 2b, 1, 3}、堆排 {21, 25, 49, 25*, 16, 08}。只写"不稳定"三个字是不够的——你无法据此判断一个没见过的变体稳不稳定。

口诀是"快选希堆不稳定"（快速、简单选择、希尔、堆），其余五种（直接插入、折半插入、冒泡、归并、基数）全稳定。

但比口诀更有用的是看清稳定性来自代码里的哪一行——四种稳定的比较排序，稳定性来源全都落在同一个位置：相等时选谁。

算法	保证稳定的那一行	破坏它会怎样
直接插入	从后向前扫，遇到 A[j] == temp 就停止，把 temp 放它后面	把 A[j] > temp 写成 >=，相等元素被越过，变不稳定
折半插入	折半查找中 A[mid] == temp 时令 low = mid + 1，往右找	改成往左找，插入位置落到相等元素之前，变不稳定
起泡	相邻元素相等时不交换（判据是 > 而不是 >=）	写成 >= 会让相等元素互换，变不稳定
二路归并	两段首元素相等时优先取左段（判据是 <= 而不是 <）	写成 < 会让右段的相等元素抢到前面，变不稳定

稳定性不是算法的玄学属性，是某一个比较符号的直接后果。

稳定性唯一真正有用的场合：多关键字排序

要把学生记录先按班级、班级相同再按成绩排列，标准做法是：

1. 先按次关键字（成绩）排一遍，用什么算法都行；
2. 再按主关键字（班级）排一遍，这一遍必须用稳定排序。

第 2 遍稳定，才能保证同一班级内部仍保持第 1 遍留下的成绩次序；若第 2 遍用了快排，同班记录会被打乱，第 1 遍白做。

这条正是基数排序正确性的基础——它就是"从低位到高位做 $d$ 遍单关键字排序"，每一遍都必须稳定。真题也直接考过这个场景：给出"先按课程 1 成绩升序、成绩相同再按总分升序"的需求问选哪个算法，答案是基数排序，理由就是它是教材里专为多关键字排序设计的那一个。

⚠️ 稳定性与效率无关，不稳定 $\ne$ 不好。 快排平均最快但不稳定，归并稳定但要 $O(n)$ 辅助空间。稳定性是功能指标，不是效率指标。

内排与外排的分界，不是数据量

分类	定义	瓶颈
内部排序	待排序记录全部存放在内存中完成排序	CPU 的比较与移动次数
外部排序	记录太多内存装不下，排序过程中尚需对外存进行访问	磁盘读写次数

🔴 分界不是"数据多不多"，而是"排序过程中要不要访问外存"。 一旦跨过这条线，优化目标就整个换了：从"比较 + 移动"变成"归并趟数"。

同一个"归并"操作，在内部排序里追求"每层 $O(n)$ 次比较"，在外部排序里追求"归并趟数 $\lceil {\log }_{k}m\rceil$ 尽量小"。真题问过"对 10TB 的数据文件进行排序应使用什么方法"，答归并排序——不是因为它比较次数少，而是因为只有它能在不把全部数据装进内存的前提下工作。

时间要拆成两项：比较次数与移动次数

这不是形式主义，两个指标的单位代价差得很远，而且互相独立：

• 一次交换要写三条赋值语句（t=a; a=b; b=t;），而插入类的一次后移只写一条。所以同为 $O(n^2)$，直接插入排序的实际移动开销约为起泡排序的三分之一。
• 记录越大，移动一条越贵，比较却不变贵。 记录很大时应当选"移动次数少"的算法——简单选择排序最坏也只移动 $3(n-1)$ 次，这是它唯一的优势，真题正面考过。
• 两者对初始序列的敏感性甚至相反：简单选择排序的比较次数恒为 $n(n-1)/2$、与初始序列无关，移动次数却随初始序列变；折半插入排序的比较次数几乎只由 $n$ 决定，移动次数却完全随初始序列变。

合并成一个数，这些结论就全看不见了——而它们恰恰是真题最爱问的。

空间只数辅助空间，即除存放待排序记录本身之外还需要的存储。理想值 $O(1)$，称为原地排序。

辅助空间来源	出现在	量级
暂存一条记录的单元（哨兵 / temp）	插入类、交换类、选择类	$O(1)$
递归工作栈	快速排序、递归写法的归并排序	与递归深度同阶
辅助数组 / 队列	归并的 $B[]$、基数的 $r$ 个队列	与数据规模或基数同阶

⚠️ 递归栈必须计入。 快速排序常被称作"原地排序"，指的是它不需要与 $n$ 同阶的辅助数组；但递归栈是真实开销，最坏可达 $O(n)$。说快排空间 $O(1)$ 是错的。

"一趟"在九种算法里指的不是同一件事

这一条是由中间状态反推排序算法那一整类题目的前提，值得单独记。"一趟排序"的通用定义是"使有序区中记录数目增加一个或几个的操作"，但落到具体算法上差别很大：

算法	一趟 =	一趟后有序区变成	趟数
直接插入 / 折半插入	把第 $i$ 个记录插入前 $i-1$ 个已排好的记录中	前 $i$ 个局部有序（未必是全局最小的 $i$ 个）	固定 $n-1$
希尔	用一个增量 $d$ 对全部 $d$ 个子序列各做一次插入排序	间隔 $d$ 的各子序列分别有序	增量序列长度 $t$
起泡	从头到尾扫一遍，逐对相邻元素比较并在逆序时交换	一端多出一个全局最值且已就位	最多 $n-1$，可提前终止
快速	一次 Partition，把一个枢轴放到最终位置	该枢轴归位，左右各成一个待排子表	= 递归树深度，随输入变
简单选择	在无序区扫一遍选出最小者，与无序区首元素交换	前 $k$ 个是全局最小的 $k$ 个且有序	固定 $n-1$
堆	堆顶与当前末元素交换 + 一次筛选调整	尾部 $k$ 个是全局最大的 $k$ 个且有序	固定 $n-1$（建初堆不计入）
二路归并	把当前所有相邻子表两两归并一遍	若干等长段各自有序，段长 $2^k$	固定 $\lceil {\log }_{2}n\rceil$
基数（LSD）	对一位做一次分配 + 一次收集	按已处理的低 $k$ 位整体有序	固定 $d$

三处最容易出错：

1. 希尔的一趟是"一个增量"，不是"一个子序列"——$d=4$ 时要把 4 个子序列全排完才算一趟。
2. 快排的趟与递归深度绑定，第 $k$ 趟归位的元素个数不是 $k$，而是至少 $k$、最多 $2^k-1$。它是唯一趟数不固定的算法。
3. 插入类的"前缀有序" $\ne$ "前缀就位"——这是区分插入与选择的唯一判据，也是这类题的核心分水岭。

五大类：按"用什么办法扩大有序区"分

分类	扩大有序区的办法	代表算法	共同特征
插入类	把无序区的一个记录插入到有序区的适当位置	直接插入、折半插入、希尔	有序区是前缀，但前缀元素不一定在最终位置
交换类	通过交换把无序区中最大/最小的记录换到位	起泡、快速	每趟至少有一个记录到达最终位置
选择类	从无序区选出最值接到有序区末尾	简单选择、堆	每趟恰有一个记录到达最终位置，且是全局最值
归并类	把两个有序区合并成更大的有序区	二路归并	有序区是若干等长段，段长每趟翻倍
分配类	不比较关键字，按各位的值做分配与收集	基数	唯一能突破 $\mathrm{\Omega }(n\log n)$ 下界的一类

右列不是背景知识，它就是反推排序算法的全部依据：一趟结束后数组长什么样，完全由"这一类算法怎么扩大有序区"决定。

比较类排序的下界

🔴 任何基于关键字比较的排序算法，最坏情况下至少需要 $\mathrm{\Omega }(n{\log }_{2}n)$ 次比较。

推导（决策树模型）：把算法的执行过程画成一棵判定树——每个内部结点是一次"$K_i$ 与 $K_j$ 谁大"的比较，结果只有两种，所以是二叉树；每条根到叶的路径对应一次完整执行。算法必须对 $n$ 个元素的每一种初始排列都正确，而共有 $n!$ 种排列，故叶结点数 $\ge n!$。高度为 $h$ 的二叉树最多 $2^h$ 个叶结点，于是 $2^h\ge n!$，即 $h\ge {\log }_2(n!)=\mathrm{\Theta }(n{\log }_{2}n)$。∎

三条适用边界比结论本身更重要：

• 它只约束以"比较关键字"为唯一信息来源的算法。基数排序与计数排序直接用关键字的取值去索引桶，信息来源不同，不受此界。
• 它是最坏情况下界，不排除某个算法在特定输入上跑出 $O(n)$——直接插入排序对已有序输入只比较 $n-1$ 次。
• 归并排序与堆排序的最坏 $O(n{\log }_{2}n)$ 正好达到这个下界，所以在比较类里它们的最坏情况已无法再改进。

考点速记

三条结论：

1. 稳定性是对所有输入的性质，一个反例即可推翻；它的根源永远是代码里"相等时选谁"那一个比较符号。快选希堆不稳定。
2. 时间必须拆成比较与移动两项，两者的单位代价和对初始序列的敏感性都不同。
3. "一趟"在九种算法里指的不是同一件事，希尔按增量数、快排按递归深度数。

这一节在真题里被考过的形式（本篇的概念被整章反复调用，下方「真题练习」只挂到直接以"排序"立题的那道大题；概念判断类的题目挂在《排序算法对比》下）：

• 应用排序思想设计算法（大题）：给一个正整数集合，要求划分成两个子集使 $|n_1-n_2|$ 最小且 $|S_1-S_2|$ 最大——本质是"找中位数再分两半"，用快速排序的 Partition 思想做，平均 $O(n)$，比先整体排序再分快一个量级。排序这一章的大题通常不是"写一个排序算法"，而是"把某个排序的核心操作用在别处"。
• 概念判断类（挂在对比那篇）：稳定性判断、"每趟至少确定一个元素最终位置"的是哪几个、选算法要考虑哪些因素、多关键字排序选哪个算法。

易错：举稳定性反例时，序列里必须有一对相等的关键字。 全不相同的例子什么也证明不了。

易错：快排的空间不是 $O(1)$。 递归栈平均 $O({\log }_{2}n)$、最坏 $O(n)$，必须计入。

易错：内排与外排的分界是"要不要访问外存"，不是数据量大小。

教材出处

• 排序的形式化定义（式 8-1～8-3）、稳定性定义与"只要有一组关键字实例不满足稳定性要求，该方法就是不稳定的"：严蔚敏《数据结构（C 语言版）》（第 2 版），p234–p235
• 内部排序与外部排序的划分、"使有序区中记录的数目增加一个或几个的操作称为一趟排序"、五大类划分：同书 p235
• 评价指标（执行时间由比较次数与移动次数决定；辅助空间的定义与 $O(1)$ 的理想值）：同书 p236
• 各种内部排序方法的时间/空间/稳定性汇总表（表 8.2）与选用原则：同书 p267–p268

相关知识

直接插入排序｜折半插入排序｜希尔排序｜ 起泡排序｜快速排序｜简单选择排序｜堆排序｜ 二路归并排序｜基数排序｜计数排序｜ 外部排序（分界之后的另一套优化目标）｜ 排序算法对比（本篇全部指标在九种算法上的取值总表）｜ 由中间状态反推排序算法｜ 算法的时间复杂度

相关文章

• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

真题练习

相关真题（1题）

2016Q4315分