排序¶
方法速览¶
| 任务 | 结论 | 口诀 |
|---|---|---|
| 稳定性 | 稳：冒泡/插入/归并/计数；不稳：选择/快排/堆 | 冒插归计稳，选快堆不稳 |
| 最坏低于 \(O(n^2)\) | 归并、堆（保证 \(O(n\log n)\)） | 归并保底 |
| 快排 + 已序 + 首元素基准 | 退化 \(O(n^2)\)（每次分出一侧空） | 已序取头必退化 |
| 基数排序个别数据异常 | 其余数据仍各自有序——整体仍有序 | 逐位独立 |
| 同时找 max 与 min | 成对比较：\(\lceil 3n/2 \rceil - 2\) | 两两结对 |
稳定性与复杂度总表¶
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡 | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | ✓ |
| 插入 | \(O(n^2)\)（近有序 \(O(n)\)） | \(O(n^2)\) | \(O(1)\) | ✓ |
| 选择 | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | ✗ |
| 快排 | \(O(n\log n)\) | \(O(n^2)\) | \(O(\log n)\) | ✗ |
| 归并 | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n)\) | ✓ |
| 堆排 | \(O(n\log n)\) | \(O(n\log n)\) | \(O(1)\) | ✗ |
| 计数 | \(O(n+M)\) | \(O(n+M)\) | \(O(M)\) | ✓ |
S 卷考点集中在最坏保证与退化条件，不是写代码。
快排的退化¶
【是什么】 快排每次选基准把数组分成两半；分得越均匀越快。
【例】（2023 真题）已排序数组 + 总取第一个元素做基准：每轮基准都是当前最小（最大），一侧恒空——划分 \(n-1\) 次、每次扫剩余全部，总代价
对策：随机选基准 / 三数取中。
基数排序的容错¶
【是什么】 基数排序按位（低位到高位）逐趟分配收集，每位独立稳定。
【例】（2022 真题）某个数据被宇宙射线改成一个完全不同的值：它只是“带着一个错误值参加了每一趟”，其余数据之间的相对秩序不受影响——移除坏数据后序列仍然有序。
相邻交换与逆序对¶
【是什么】 每次交换相邻两个元素，一次恰好消除一个逆序对——把序列变有序的最少交换次数 \(=\) 逆序对数。
【例】（2021 真题）DACFEB 变成 ABCDEF：以目标序为标准，逆序对为 (D,A)(D,C)(F,E)(D,B)(F,B)(E,B)(C,B) 共 7 对——最少交换 7 次（程序枚举验证）。
【例】（2024 真题）长度 n 的 01 串、k 个 1 移到最右：最坏（1 全在左）时每个 1 越过全部 \(n-k\) 个 0 → \((n-k)\,k\) 次；1 之间的相对顺序无需交换。
练习题目¶
练习 1 · 不稳定排序识别¶
题目
下列排序中不稳定的是（ ）
- A. 冒泡排序
- B. 直接插入排序
- C. 堆排序
- D. 归并排序
答案与解析
答案：C
选快堆不稳；堆的远距离交换会跨越相等元素。
练习 2 · 不稳定（快排）¶
题目
下列排序中不稳定的是（ ）
- A. 快速排序
- B. 折半插入排序
- C. 冒泡排序
- D. 计数排序
答案与解析
答案：A
快排的划分交换会打乱相等元素的相对顺序。
练习 3 · 最坏保证¶
题目
对 n 个数排序，最坏时间复杂度低于 \(O(n^2)\) 的是（ ）
- A. 快速排序
- B. 直接插入排序
- C. 归并排序
- D. 冒泡排序
答案与解析
答案：C
归并任何输入都是 \(O(n\log n)\)；快排最坏 \(O(n^2)\)（快排是平均 \(n\log n\)）。
练习 4 · 快排最好情形¶
题目
快排达到 \(O(n\log n)\) 的条件（ ）
- A. 输入已排序
- B. 每次划分大致均匀
- C. 元素互异
- D. 递归深度为 n
答案与解析
答案：B
均匀划分 → 递归深度 \(\log n\)、每层 \(O(n)\)。
练习 5 · 退化输入¶
题目
使“首元素为基准”的快排退化为 \(O(n^2)\) 的输入是（ ）
- A. 已排序数组
- B. 随机数组
- C. 全部元素相等
- D. A 和 C 都是
答案与解析
答案：D
已序与全相等都使划分恒为一侧空/极不均；随机化基准可规避。
练习 6 · 归并的比较次数¶
题目
归并两个长度分别为 a、b 的有序数组，最坏比较次数（ ）
- A. \(a + b\)
- B. \(a + b - 1\)
- C. \(\min(a,b)\)
- D. \(ab\)
答案与解析
答案：B
每次比较至少归位一个元素，最后剩一个免比较：\(a+b-1\)。
练习 7 · 同时找最大最小¶
题目
两两结对比较（先组内比、大者跟最大比、小者跟最小比），n 个数（偶数）同时找 max/min 的比较次数为（ ）
- A. \(3n/2 - 2\)
- B. \(2n - 2\)
- C. \(2n - 3\)
- D. \(n\log n\)
答案与解析
答案：A
结内 \(\frac n2\) 次 + 每个大者对 max、小者对 min 各 \(\frac n2 - 1\) 次：\(\frac n2 + (\frac n2 - 1)\times2 = \frac{3n}2 - 2\)。
练习 8 · 比较下界¶
题目
基于比较的排序算法的时间复杂度下界是（ ）
- A. \(O(\log n)\)
- B. \(O(n)\)
- C. \(O(n^2)\)
- D. \(O(n\log n)\)
答案与解析
答案：D
n! 种排列需 \(\log_2 n! \approx n\log n\) 次比较区分——计数/基数不基于比较才能突破。
练习 9 · 堆排空间¶
题目
堆排序的空间复杂度是（ ）
- A. \(O(n\log n)\)
- B. \(O(n)\)
- C. \(O(\log n)\)
- D. \(O(1)\)
答案与解析
答案：D
原地建堆、原地取顶下沉——不耗辅助数组（归并才要 \(O(n)\)）。
练习 10 · 基数排序复杂度¶
题目
n 个 d 位数、每位 k 种取值，基数排序的时间复杂度是（ ）
- A. \(O(n \log n)\)
- B. \(O(d\cdot(n+k))\)
- C. \(O(n^2)\)
- D. \(O(d\cdot n\log k)\)
答案与解析
答案：B
d 趟分配收集，每趟 \(O(n+k)\)——位数固定时线性。
练习 11 · 基数排序前提¶
题目
基数排序不适用 / 效率差的场景（ ）
- A. 大量整数按位排序
- B. 定长字符串排序
- C. 无法按位分解的比较（如任意实数）
- D. 日期排序
答案与解析
答案：C
基数排序要能把键按位分解成有限符号集；任意实数没有“位”。
练习 12 · 稳定性的用途¶
题目
多关键字排序中需要稳定性的原因是（ ）
- A. 减少比较次数
- B. 防止死循环
- C. 节省内存
- D. 后一轮排序不打散前一轮相等元素的成果
答案与解析
答案：D
依次按低关键字到高关键字排序，稳定性保证早先的次序保留。
练习 13 · top-k 问题¶
题目
1 亿个数找最大的 100 个，最省内存的做法（ ）
- A. 全排序取前 100
- B. 维护 100 大小的小根堆，流式更新
- C. 桶排
- D. 二分查找
答案与解析
答案：B
堆只占 100 个元素空间、一遍扫描 \(O(n\log k)\)；全排序要装下全部数据。
练习 14 · 归并的空间¶
题目
归并排序需要 \(O(n)\) 辅助数组的根本原因是（ ）
- A. 递归栈
- B. 合并两段时不能原地交错（一般实现需暂存输出）
- C. 需要哈希表
- D. 数据太大
答案与解析
答案：B
合并阶段要按序产出，经典实现把结果写入临时数组再拷回；递归栈只是 \(O(\log n)\)。
练习 15 · 快排空间¶
题目
快排的平均空间复杂度（递归栈）（ ）
- A. \(O(1)\)
- B. \(O(\log n)\)
- C. \(O(n)\)
- D. \(O(n\log n)\)
答案与解析
答案：B
均匀划分递归深度 \(\log n\)；退化时深度 n → 空间也退化 \(O(n)\)。
练习 16 · 插入排序最佳¶
题目
插入排序在（ ）输入下达到 \(O(n)\)。
- A. 逆序
- B. 已升序
- C. 随机
- D. 全相等
答案与解析
答案：B
每个新元素与前一比即停；全相等其实也是 \(O(n)\)（都不移动），但标准答案是已升序。
练习 17 · 选择排序交换数¶
题目
选择排序 n 个元素的交换次数至多（ ）
- A. \(n - 1\)
- B. \(\frac{n(n-1)}{2}\)
- C. \(n\)
- D. \(n\log n\)
答案与解析
答案：A
每轮至多换一次；比较次数才是 \(\frac{n(n-1)}{2}\)。
练习 18 · 归并趟数¶
题目
对 8 个长度为 1 的有序段自底向上归并，需要（ ）趟。
- A. \(3\)
- B. \(4\)
- C. \(8\)
- D. \(2\)
答案与解析
答案：A
\(8\to4\to2\to1\)，\(\log_2 8 = 3\) 趟。
练习 19 · 计数排序空间¶
题目
计数排序值域 \(10^9\)（n 仅 \(10^5\)）不可行的原因是（ ）
- A. 时间 \(O(n\log n)\) 太慢
- B. 桶数组空间 \(O(M)\) 爆内存
- C. 不稳定
- D. 只能排字符串
答案与解析
答案：B
空间随值域而不是 n 开销。
练习 20 · 排序算法选择¶
题目
n = 10⁶、内存充裕、要求稳定且保证 \(O(n\log n)\)，选（ ）
- A. 快速排序
- B. 堆排序
- C. 归并排序（stable_sort）
- D. 选择排序
答案与解析
答案：C
同时满足“稳定 + 最坏保证”的只有归并；快排不稳且最坏平方。
练习 21 · 外排序¶
题目
数据远大于内存时的排序方法是（ ）
- A. 内排序
- B. 哈希排序
- C. 快速排序
- D. 外排序（分块 + 多路归并）
答案与解析
答案：D
内存装不下就分块排好写回外存，再 k 路归并——瓶颈是 I/O。
练习 22 · 逆序对与冒泡¶
题目
冒泡排序的交换次数等于数组的（ ）
- A. 最大值
- B. 元素个数
- C. 比较次数
- D. 逆序对数
答案与解析
答案：D
每次相邻交换恰消除一个逆序对；归并排序能 \(O(n\log n)\) 数逆序对。
练习 23 · 快排第 k 小¶
题目
基于快排划分找第 k 小元素，平均时间复杂度（ ）
- A. \(O(n)\)
- B. \(O(n\log n)\)
- C. \(O(n^2)\)
- D. \(O(\log n)\)
答案与解析
答案：A
每次只递归一侧，\(n + n/2 + n/4 + \cdots < 2n\)。
练习 24 · 堆的建立¶
题目
自底向上建堆（Floyd 法）的时间复杂度是（ ）
- A. \(O(n)\)
- B. \(O(n\log n)\)
- C. \(O(\log n)\)
- D. \(O(n^2)\)
答案与解析
答案：A
多数结点下沉距离小，总和收敛到 \(O(n)\)——比逐个插入建堆（\(O(n\log n)\)）快。
练习 25 · 稳定性反例¶
题目
选择排序不稳定的一个最小反例（键值对 \((a,1),(a,2),(b,3)\) 按键排序）体现在（ ）
- A. 键相等时崩
- B. 无法比较
- C. \((a,2)\) 会与 \((b,3)\) 远距离交换后越过 \((a,1)\)
- D. 没有反例
答案与解析
答案：C
第一轮最小是 \((a,1)\) 已就位不换；关键是 \((a,2)\) 与更小键的远距离交换可能跨越相等键——标准反例：\((3a, 3b, 1)\) 首轮 1 与 3a 换位，3a 越过 3b。
练习 26 · 综合判定¶
题目
下列说法错误的是（ ）
- A. 归并稳定且最坏 \(O(n\log n)\)
- B. 快排平均 \(O(n\log n)\)、最坏 \(O(n^2)\)
- C. 堆排稳定
- D. 插入排序对近有序数据高效
答案与解析
答案：C
堆排不稳定。
练习 27 · 逆序对计数（小）¶
题目
312 的逆序对数是（ ）
- A. \(0\)
- B. \(1\)
- C. \(3\)
- D. \(2\)
答案与解析
答案：D
(3,1)、(3,2) 两对——大数在小数前。
练习 28 · 相邻交换排序¶
题目
只交换相邻元素把 21 排成升序需要（ ）次。
- A. \(0\)
- B. \(2\)
- C. \(3\)
- D. \(1\)
答案与解析
答案：D
一个逆序对、一次交换——次数恒等于逆序对数。
练习 29 · 变形词交换¶
题目
把 BA 变成 AB（相邻交换）最少（ ）次。
- A. \(3\)
- B. \(2\)
- C. \(1\)
- D. \(0\)
答案与解析
答案：C
一个逆序对 (B, A)。
练习 30 · 逆序对上界¶
题目
长度 n 的序列最多（ ）个逆序对。
- A. \(\binom n2\)
- B. \(n\)
- C. \(n\log n\)
- D. \(n - 1\)
答案与解析
答案：A
完全倒序时每一对都是逆序对——也是冒泡最坏交换次数。
练习 31 · 01 串移动（最多）¶
题目
长度 10 的 01 串含 4 个 1，全部移到最右最多需要（ ）次相邻交换。
- A. \(24\)
- B. \(16\)
- C. \(40\)
- D. \(6\)
答案与解析
答案：A
\((n-k)k = 6\times4 = 24\)——每个 1 越过每个 0（2024 真题公式）。
练习 32 · 01 串移动（最少）¶
题目
同上一题设定，最少需要（ ）次。
- A. \(0\)
- B. \(24\)
- C. \(10\)
- D. \(4\)
答案与解析
答案：A
若串本来就是 0000111111（1 全在右侧）则 0 次——问最少先看已就位情形。
练习 33 · 逆序对的线性对统计¶
题目
\(O(n\log n)\) 统计逆序对的算法基于（ ）
- A. 归并排序（合并时数跨对）
- B. 快速排序
- C. 哈希
- D. 前缀和
答案与解析
答案：A
merge 时右段先出，累计左段剩余长度——分治数对。
练习 34 · 交换下界¶
题目
只用相邻交换把序列变有序，交换次数至少是（ ）
- A. 逆序对数
- B. n
- C. \(\log n\)
- D. 任意
答案与解析
答案：A
每次交换至多消一个逆序对——下界即逆序对数，冒泡恰好达到。
历年真题¶
2019 年 · 第 7 题¶
题目
排序的算法很多，若按排序的稳定性和不稳定性分类，则（ ）是不稳定排序。
- A. 快速排序
- B. 直接插入排序
- C. 归并排序
- D. 冒泡排序
答案与解析
答案：A
选快堆不稳；B/C/D 都稳定。
2021 年 · 第 4 题¶
题目
以下排序方法中，（ ）是不稳定的。
- A. 插入排序
- B. 冒泡排序
- C. 堆排序
- D. 归并排序
答案与解析
答案：C
两年换着考不稳定名单：2019 问快排、2021 问堆。
2021 年 · 第 10 题¶
题目
定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF 最少需要（ ）次上述操作。
- A. \(7\)
- B. \(8\)
- C. \(9\)
- D. \(6\)
答案与解析
答案：A
相邻交换次数 = 逆序对数：以目标序 ABCDEF 为标准，逆序对为 (D,A)(D,C)(F,E)(D,B)(F,B)(E,B)(C,B) 共 7 对（程序枚举验证，完整演算见“相邻交换与逆序对”节）。
2022 年 · 第 4 题¶
题目
考虑对 \(n\) 个数进行排序，以下最坏时间复杂度低于 \(O(n^2)\) 的排序方法是（ ）。
- A. 插入排序
- B. 冒泡排序
- C. 归并排序
- D. 快速排序
答案与解析
答案：C
“最坏”是关键词：快排最坏平方，只有归并（和堆）保 \(O(n\log n)\)。
2022 年 · 第 5 题¶
题目
假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ）。
- A. 移除受影响的数据后，最终序列是有序序列。
- B. 移除受影响的数据后，最终序列是前后两个有序的子序列。
- C. 移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列。
- D. 移除受影响的数据后，最终序列基本无序。
答案与解析
答案：A
基数排序逐位独立：坏数据只影响自己所在的位置，其余数据的相对顺序不被破坏——移除后仍有序。
2023 年 · 第 10 题¶
题目
假设快速排序算法的输入是一个长度为 \(n\) 的已排序数组，且该快速排序算法在分治过程中总是选择第一个元素作为基准元素。以下哪个选项描述的是这种情况下的快速排序行为？（ ）
- A. 快速排序对于此类输入的表现最好，因为数组已经排序。
- B. 快速排序对于此类输入的时间复杂度是 \(O(n\log n)\)。
- C. 快速排序对于此类输入的时间复杂度是 \(O(n^2)\)。
- D. 快速排序无法对此类数组进行排序，因为数组已经排序。
答案与解析
答案：C
已序 + 首元素基准 → 每轮划分一侧为空，递归深度 n：\(n+(n-1)+\cdots = O(n^2)\)（完整推导见教学节）。
2024 年 · 第 14 题¶
题目
设有一个长度为 \(n\) 的 \(01\) 字符串，其中有 \(k\) 个 \(1\)。每次操作可以交换相邻两个字符。在最坏情况下将这 \(k\) 个 \(1\) 移到字符串最右边所需要的交换次数是多少？
- A. \(k\)
- B. \(\frac{k(k-1)}{2}\)
- C. \((n-k)k\)
- D. \(\frac{(2n-k-1)k}{2}\)
答案与解析
答案：C
最坏（1 全在左侧）时每个 1 越过全部 \(n-k\) 个 0：\((n-k)\,k\)；1 之间的相对顺序不需交换。
易错小结¶
- 稳定名单“冒插归计稳，选快堆不稳”（2019 快排 / 2021 堆两次考）；
- “最坏低于 \(n^2\)”只有归并/堆——快排是平均 \(n\log n\)（2022 反向词陷阱）；
- 快排退化三件套：已序输入 + 首元素基准 + 不随机化；
- 基数排序按位独立，个别坏数据不传染（2022）；
- 成对比较同时找 max/min：\(\lceil 3n/2\rceil - 2\)；比较排序下界 \(n\log n\)；
- 堆排空间 \(O(1)\)、归并空间 \(O(n)\)；自底向上建堆 \(O(n)\)；
- 大数据找 top-k 用小根堆流式处理；
- 相邻交换次数 = 逆序对数；k 个 1 移到最右最坏 \((n-k)k\) 次（2021/2024 两道真题）。