排序¶

方法速览¶

任务	方法	口诀
冒泡交换次数	\(=\) 数组的逆序对数	冒泡一次消一对
冒泡趟数	每趟至少归位一个最大值；有序提前停	一趟冒一个
稳定性	稳定：冒泡、插入、归并、计数；不稳：选择、快排、堆	冒插归计稳，选快堆不稳
std::sort	不保证稳定，要稳定用 `stable_sort`	sort 不稳
内外排序	数据放内存 = 内排序；放外存分批归并 = 外排序	装得下内存，装不下外存

冒泡排序（代码 + 两种优化 + 逆序对）¶

基础版——相邻逆序就交换，每趟把当前最大值“冒”到末尾：

for (int i = 1; i < n; i++)            // 共 n-1 趟
    for (int j = 1; j <= n - i; j++)   // 每趟少比一个
        if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);

优化一（无交换提前退出）：某趟一次交换都没发生，说明已经有序：

for (int i = 1; i < n; i++) {
    bool flag = false;
    for (int j = 1; j <= n - i; j++)
        if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = true; }
    if (!flag) break;                  // 本趟无交换 → 已有序
}

优化二（记忆最后交换位置）：某趟最后一次交换发生在位置 j，说明 j 之后已经有序，下一趟只扫到 j：

FLAG ← n
while FLAG > 1:
    k ← FLAG − 1;  FLAG ← 1
    for j = 1 to k:
        if L(j) > L(j+1): 交换；FLAG ← j

例：数组 \(\{6,1,5,2,4\}\) 逐趟演算：

趟	过程	结果
1	6↔1、6↔5、6↔2、6↔4（4 次交换）	`1 5 2 4 6`
2	5↔2、5↔4（2 次）	`1 2 4 5 6`
3	无交换，提前结束	`1 2 4 5 6`

共交换 6 次——恰好等于该数组的逆序对数（\(\{6,1\},\{6,5\},\{6,2\},\{6,4\},\{5,2\},\{5,4\}\) 共 6 对）：冒泡的每次交换恰好消除一个逆序对，所以交换次数 = 逆序对数。

选择排序¶

每轮从未排序区间挑最小的换到最前：

for (int i = 1; i < n; i++) {
    int m = i;
    for (int j = i + 1; j <= n; j++)
        if (a[j] < a[m]) m = j;
    if (m != i) swap(a[i], a[m]);   // 每轮至多交换 1 次
}

特点：比较次数固定 \(\frac{n(n-1)}{2}\)（与数据无关）；交换至多 n−1 次——数据移动量最小。\(\{6,1,5,2,4\}\) 只交换 4 次（每轮一次）。

插入排序¶

像理扑克牌：把新牌插进已排序的前缀：

for (int i = 2; i <= n; i++) {
    int x = a[i], j = i - 1;
    while (j >= 1 && a[j] > x) { a[j + 1] = a[j]; j--; }  // 大于 x 的整体后移
    a[j + 1] = x;
}

特点：基本有序时接近 \(O(n)\)；移动次数 = 逆序对数（与冒泡的交换次数一致，只是“搬”不是“换”）。

计数排序¶

值域小（如 \(0 \sim 10^6\)）时开桶数组直接数：

int cnt[M];
for (int i = 1; i <= n; i++) cnt[a[i]]++;
for (int v = 0, k = 1; v < M; v++)
    while (cnt[v]--) a[k++] = v;

\(O(n + M)\)，非比较排序，突破 \(O(n\log n)\) 下界（代价是吃内存）。

sort / 自定义 / 结构体排序¶

sort(a + 1, a + n + 1);                          // 默认升序
sort(a + 1, a + n + 1, greater<int>());          // 降序
bool cmp(int x, int y) { return x > y; }         // 自定义：cmp 定义“谁在前”
sort(a + 1, a + n + 1, cmp);

struct P { int x, y; };
bool cmp2(const P& a, const P& b) {              // 结构体多关键字
    if (a.x != b.x) return a.x < b.x;            // 第一关键字 x 升
    return a.y > b.y;                            // 第二关键字 y 降
}

sort 是 introsort（快排+堆排+插入混合），平均 \(O(n\log n)\)；cmp 里相等必须返回 false。

排序的稳定性¶

稳定：排序后相等元素的相对先后保持不变。

稳定	不稳定
冒泡、插入、归并、计数	选择、快速、堆

选择排序不稳的原因：swap 可能跳过与当前最小值相等的元素；
std::sort 不保证稳定，要稳定用 stable_sort（归并实现）。

内排序与外排序¶

内排序：数据全部装进内存里排（上面全部算法）；
外排序：数据大到内存装不下，放外存（磁盘），分块读入排好写回，再多路归并——瓶颈是磁盘 I/O 次数，不是比较次数。

练习题目¶

练习 1 · 冒泡的交换次数¶

题目

用冒泡排序把 \(\{3, 2, 1\}\) 升序排列，共交换（）次。

A. \(2\)
B. \(6\)
C. \(1\)
D. \(3\)

答案与解析

答案：D

逆序对 \(\{3,2\},\{3,1\},\{2,1\}\) 共 3 对 = 交换 3 次。

练习 2 · 交换次数 = 逆序对数¶

题目

冒泡排序的交换次数等于数组的（）

A. 元素个数
B. \(\frac{n(n-1)}{2}\)
C. 逆序对数
D. 任意

答案与解析

答案：C

每次相邻交换恰好消除一个逆序对，消完即有序。

练习 3 · 已有序数组的冒泡¶

题目

对已经升序的 n 个数跑带“无交换提前退出”的冒泡，比较次数是（）

A. \(\frac{n(n-1)}{2}\)
B. \(n\)
C. \(n - 1\)
D. \(0\)

答案与解析

答案：C

第一趟扫完 \(n-1\) 次比较、零交换 → 提前退出。没有优化一则要跑满 \(\frac{n(n-1)}{2}\) 次。

练习 4 · 一趟归位几个¶

题目

冒泡排序（从左往右、大数右沉）每一趟能保证（）

A. 最小值到最左
B. 未排序区间的最大值到最终位置
C. 全部有序
D. 前两个有序

答案与解析

答案：B

大数一路被换到未排序区间的末端；注意方向反过来（从右往左小数左浮）则归位最小值。

练习 5 · 冒泡趟数¶

题目

\(\{5, 4, 3, 2, 1\}\)（完全逆序，n=5）冒泡需要（）趟。

A. \(5\)
B. \(4\)
C. \(3\)
D. \(2\)

答案与解析

答案：B

每趟归位一个最大值，n−1 = 4 趟全归位（最坏情形趟数）。

练习 6 · 逆序对计数¶

题目

\(\{4, 2, 5, 1, 3\}\) 的逆序对数是（）

A. \(4\)
B. \(5\)
C. \(6\)
D. \(7\)

答案与解析

答案：C

逐个元素数它后面比它小的：

元素	后面比它小的	对数
4	2, 1, 3	3
2	1	1
5	1, 3	2
1	无	0

共 \(3+1+2 = 6\) 对（\(\{4,2\},\{4,1\},\{4,3\},\{2,1\},\{5,1\},\{5,3\}\)）。

练习 7 · 逆序对上限¶

题目

n 个互不相同元素的数组，逆序对最多（）个。

A. \(n^2\)
B. \(n - 1\)
C. \(n\log n\)
D. \(\dfrac{n(n-1)}{2}\)

答案与解析

答案：D

完全逆序时每一对都是逆序对，共 \(\binom{n}{2}\) 个——这也是冒泡最坏交换次数。

练习 8 · 选择排序交换数¶

题目

选择排序 n 个元素，交换次数至多（）次。

A. \(\frac{n(n-1)}{2}\)
B. \(n - 1\)
C. \(n\)
D. \(\frac{n(n-1)}{4}\)

答案与解析

答案：B

每轮至多换一次（最小值到位），共 n−1 轮——比较次数才是 \(\frac{n(n-1)}{2}\)。

练习 9 · 选择排序比较数¶

题目

选择排序对 n 个元素的比较次数是（）（与初始顺序无关）

A. \(n - 1\)
B. \(\frac{n(n-1)}{2}\)
C. \(n\log n\)
D. 视数据而定

答案与解析

答案：B

第 i 轮扫 \(n-i\) 次，总和 \(\frac{n(n-1)}{2}\)——有序数组也照扫不误。

练习 10 · 插入排序最佳情形¶

题目

插入排序对已升序数组的时间复杂度是（）

A. \(O(n)\)
B. \(O(n\log n)\)
C. \(O(n^2)\)
D. \(O(1)\)

答案与解析

答案：A

每张新牌与前一比即插，总共 n−1 次比较、零移动——插入排序是“基本有序数据”的最优解。

练习 11 · 插入排序移动次数¶

题目

插入排序的元素移动次数等于（）

A. 逆序对数
B. 元素个数
C. 比较次数
D. 与逆序对无关

答案与解析

答案：A

每个逆序对对应一次后移——与冒泡的交换次数同源。

练习 12 · 计数排序的复杂度¶

题目

计数排序的时间复杂度是（）（设值域大小 M）

A. \(O(n\log n)\)
B. \(O(M\log M)\)
C. \(O(n^2)\)
D. \(O(n + M)\)

答案与解析

答案：D

数一遍 \(O(n)\)、扫桶 \(O(M)\)；它不基于比较，所以不受 \(O(n\log n)\) 下界约束。

练习 13 · 计数排序的代价¶

题目

计数排序的局限是（）

A. 结果不有序
B. 时间太慢
C. 必须递归
D. 只能排整数且值域不能太大（空间 \(O(M)\)）

答案与解析

答案：D

桶数组按值开空间：值域 \(10^9\) 直接爆内存；也不适用于浮点/字符串。

练习 14 · 稳定性的定义¶

题目

排序算法“稳定”指（）

A. 时间复杂度稳定
B. 不崩溃
C. 相等元素排序后保持原有相对顺序
D. 空间复杂度不变

答案与解析

答案：C

如两个 85 分排序后仍是原来的先后——多关键字排序时靠它保住第二关键字。

练习 15 · 不稳定的算法¶

题目

下列排序算法中不稳定的是（）

A. 冒泡排序
B. 插入排序
C. 简单选择排序
D. 归并排序

答案与解析

答案：C

口诀“冒插归计稳，选快堆不稳”。选择排序的远距离 swap 会跨过相等元素。

练习 16 · 快排的稳定性与退化¶

题目

关于快速排序，正确的是（）

A. 稳定，且任何输入都 \(O(n\log n)\)
B. 不稳定，已序输入选首元素为基准时退化为 \(O(n^2)\)
C. 稳定，最坏 \(O(n^2)\)
D. 不稳定，最好 \(O(n^2)\)

答案与解析

答案：B

已序数组 + 取头为基准 → 每次分出一侧为空，递归深度 n；随机取基准可规避。快排不稳。

练习 17 · std::sort 与 stable_sort¶

题目

要在排序时保持相等元素的相对顺序，应使用（）

A. sort
B. stable_sort
C. qsort
D. 随便哪个

答案与解析

答案：B

std::sort 不保证稳定；stable_sort（归并）才承诺。

练习 18 · 稳定性的用途¶

题目

学生记录先按总分排好，再按班级排（同班内保持总分次序），第二次排序应（）

A. 用稳定排序（或把总分作第二关键字）
B. 用任意排序
C. 用快排
D. 先打乱再排

答案与解析

答案：A

稳定性 = 后一轮不打散前一轮的成果；另一条路是把两个关键字都写进 cmp。

练习 19 · cmp 的严格性¶

题目

bool cmp(int a, int b) { return a >= b; } 配 sort 使用会（）

A. 正常降序
B. 相等时违反严格弱序，可能运行期错误
C. 变成升序
D. 编译错误

答案与解析

答案：B

比较器要求相等返回 false；降序写 a > b 即可。

练习 20 · 归并的复杂度¶

题目

归并排序的时间复杂度与空间复杂度是（）

A. \(O(n\log n)\)、\(O(n)\)
B. \(O(n^2)\)、\(O(1)\)
C. \(O(n\log n)\)、\(O(1)\)
D. \(O(n)\)、\(O(n)\)

答案与解析

答案：A

\(\log n\) 层、每层 \(O(n)\) 合并；辅助数组要 \(O(n)\)——“稳定 + 保证 \(O(n\log n)\)”是它的卖点。

练习 21 · 堆排的复杂度¶

题目

堆排序的时间复杂度与空间复杂度是（）

A. \(O(n\log n)\)、\(O(1)\)
B. \(O(n\log n)\)、\(O(n)\)
C. \(O(n^2)\)、\(O(1)\)
D. \(O(n\log n)\)、\(O(\log n)\)

答案与解析

答案：A

原地建堆、每次取顶下沉 \(O(\log n)\)；不稳定。

练习 22 · 内排序¶

题目

“内排序”指（）

A. 在内存中完成的排序
B. 排内部元素
C. 递归在内部进行
D. 只排整数

答案与解析

答案：A

数据装得进内存；装不下就得外排序。

练习 23 · 外排序¶

题目

外排序的主要瓶颈是（）

A. 比较次数
B. 磁盘 I/O 次数
C. CPU 主频
D. 显示速度

答案与解析

答案：B

数据在外存，分块调入、多路归并——访存代价远超计算。

练习 24 · 外排序的核心步骤¶

题目

外排序的标准流程是（）

A. 一次性读入内存快排
B. 分块读入各自排好写回外存，再多路归并
C. 每次交换两个元素都要写盘
D. 用哈希表

答案与解析

答案：B

内存按容量切块（顺串），归并阶段用堆维护 k 路最小值。

练习 25 · 算法选型¶

题目

\(n = 10^6\) 的整数、值域 \(0 \sim 10^7\)、要求 O(n) 级别，选（）

A. 冒泡排序
B. 选择排序
C. 插入排序
D. 计数排序

答案与解析

答案：D

值域可承受的整数排序，计数 \(O(n+M)\) 完胜比较排序的 \(O(n\log n)\)。

练习 26 · 综合判断¶

题目

下列说法错误的是（）

A. 冒泡的交换次数等于逆序对数
B. 选择排序比较次数与初始数据无关
C. 快排在最坏情况下是 \(O(n\log n)\)
D. 插入排序对基本有序的数据接近 \(O(n)\)

答案与解析

答案：C

快排最坏（已序+首元素基准）退化为 \(O(n^2)\)；A/B/D 都对。

历年真题¶

2020 年 · 第 5 题¶

题目

冒泡排序算法的伪代码如下：

输入：数组 L，n≥1。输出：按非递减顺序排序的 L。
算法 BubbleSort：
 1  FLAG ← n    //标记被交换的最后元素位置
 2  while FLAG > 1 do
 3      k ← FLAG - 1
 4      FLAG ← 1
 5      for j = 1 to k do
 6          if L(j) > L(j + 1) then do
 7              交换 L(j)、L(j+1)
 8              FLAG ← j

对 \(n\) 个数用以上冒泡排序算法进行排序，最少需要比较多少次？（）

A. \(n^2\)
B. \(n-2\)
C. \(n-1\)
D. \(n\)

答案与解析

答案：C

最少比较发生在输入已有序时：第一轮 for 扫 \(n-1\) 次比较、零交换 → FLAG 保持 1 → while 退出。共 \(n-1\) 次。

这份伪代码就是“记忆最后交换位置”优化：FLAG 始终记录本趟最后的交换点，下一趟只需扫到它。

2022 年 · 第 9 题¶

题目

以下排序算法的常见实现中，哪个选项的说法是错误的：（）。

A. 冒泡排序算法是稳定的
B. 简单选择排序是稳定的
C. 简单插入排序是稳定的
D. 归并排序算法是稳定的

答案与解析

答案：B

选择排序不稳定（远距离交换跨过相等元素）；冒泡、插入、归并都稳定——“冒插归计稳，选快堆不稳”。

2025 年 · 第 12 题¶

题目

某同学用冒泡排序对数组 {\(6, 1, 5, 2, 4\)} 进行升序排序，请问需要进行多少次元素交换？（）

A. \(5\)
B. \(6\)
C. \(7\)
D. \(8\)

答案与解析

答案：B

逆序对：\(\{6,1\},\{6,5\},\{6,2\},\{6,4\},\{5,2\},\{5,4\}\) 共 6 对 → 交换 6 次。逐趟演算见“冒泡排序”一节：第 1 趟 4 次、第 2 趟 2 次、第 3 趟 0 次收尾。

易错小结¶

交换次数 = 逆序对数（冒泡）；完全逆序时取最大 \(\binom{n}{2}\)；
有序输入 + 提前退出优化 → 冒泡只要 \(n-1\) 次比较（2020 真题）；
选择排序比较次数固定 \(\frac{n(n-1)}{2}\)、交换至多 \(n-1\) 次；
插入排序对基本有序数据近 \(O(n)\)，移动次数也是逆序对数；
稳定：冒泡/插入/归并/计数；不稳：选择/快排/堆；std::sort 不保证稳定（用 stable_sort）；
快排最坏 \(O(n^2)\)（已序+首元素基准）；归并稳定且保 \(O(n\log n)\) 但吃 \(O(n)\) 空间；
外排序瓶颈在磁盘 I/O，流程 = 分块顺串 + 多路归并。