第 7 章　基础排序与比较模型

本章解决的问题：三种最朴素的排序算法为什么还值得学？以及"排序至少要比较多少次"这个问题的答案，为什么决定了所有排序算法的上限。

7.1　冒泡、选择、插入：三种 $O(n^2)$ 排序

学习目标：学完本节，你能

手写三种 $O(n^2)$ 排序，并说清各自的比较/移动次数特征；
解释为什么选择排序的比较次数与数据无关；
说出插入排序在什么情况下能接近 $O(n)$ —— 以及这个性质在工程上的价值。

先修：1.3（最好/最坏/平均）、3.1（数组的交换）。 固定术语：冒泡排序、选择排序、插入排序、比较次数、移动次数。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：整理扑克牌的三种方式

假设你手里有一把乱序的扑克牌，要从小到大排好。三种最自然的做法：

做法	名字	类比
反复扫，看到逆序就换	冒泡排序	从头扫到尾，发现相邻两张顺序不对就交换，重复直到没有逆序
每次挑出最小的放前面	选择排序	从剩下的牌里挑出最小的一张，放到已排好的末尾
一张张插到合适的位置	插入排序	像整理手里的牌：拿起一张，插到左边已经排好序的部分里

这三种都是 $O(n^2)$ —— 但它们的"性格"完全不同，适用的场景也不同。这正是本节要讲清楚的。

二、三种实现

// 冒泡排序：相邻两个比较，大的往后冒
static (long Comparisons, long Moves) BubbleSort(int[] source)
{
    int[] a = (int[])source.Clone();
    long cmp = 0, moves = 0;
    int n = a.Length;

    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
        {
            cmp++;
            if (a[j] > a[j + 1])
            {
                (a[j], a[j + 1]) = (a[j + 1], a[j]);
                moves++;
                swapped = true;
            }
        }
        if (!swapped) break;      // 优化：一整轮都没交换，说明已经有序
    }
    return (cmp, moves);
}

// 选择排序：每轮找出最小的，和当前位置交换
static (long Comparisons, long Moves) SelectionSort(int[] source)
{
    int[] a = (int[])source.Clone();
    long cmp = 0, moves = 0;
    int n = a.Length;

    for (int i = 0; i < n - 1; i++)
    {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
        {
            cmp++;
            if (a[j] < a[minIdx]) minIdx = j;
        }
        if (minIdx != i)
        {
            (a[i], a[minIdx]) = (a[minIdx], a[i]);
            moves++;
        }
    }
    return (cmp, moves);
}

// 插入排序：把当前元素插到左边已排好序的部分里
static (long Comparisons, long Moves) InsertionSort(int[] source)
{
    int[] a = (int[])source.Clone();
    long cmp = 0, moves = 0;

    for (int i = 1; i < a.Length; i++)
    {
        int key = a[i];
        int j = i - 1;
        while (j >= 0)
        {
            cmp++;
            if (a[j] <= key) break;
            a[j + 1] = a[j];      // 注意：这是「移动」不是「交换」，一次赋值
            moves++;
            j--;
        }
        a[j + 1] = key;
    }
    return (cmp, moves);
}

两处值得注意的实现细节：

冒泡排序的 swapped 优化。 如果某一轮完全没有发生交换，说明数组已经有序，可以提前退出。这让冒泡在"已经有序"的输入上从 $O(n^2)$ 变成 $O(n)$。
插入排序用的是"移动"而不是"交换"。 冒泡的一次交换是三次赋值（需要临时变量），而插入排序的一次移动是一次赋值。这个差别在实测中会体现出来。

三、实测：四种输入下的巨大差异

数据量 5000，四种典型的输入：

  输入         | 算法       |      比较次数 |     移动次数 |      耗时
--------------------------------------------------------------------------
  随机         | 冒泡排序   |    12,490,479 |    6,158,004 |    6.3 ms
  随机         | 选择排序   |    12,497,500 |        4,995 |    3.1 ms
  随机         | 插入排序   |     6,162,995 |    6,158,004 |    1.6 ms

  已排序       | 冒泡排序   |         4,999 |            0 |    0.0 ms
  已排序       | 选择排序   |    12,497,500 |            0 |    2.5 ms
  已排序       | 插入排序   |         4,999 |            0 |    0.0 ms

  完全逆序     | 冒泡排序   |    12,497,500 |   12,497,500 |    6.8 ms
  完全逆序     | 选择排序   |    12,497,500 |        2,500 |    3.7 ms
  完全逆序     | 插入排序   |    12,497,500 |   12,497,500 |    3.3 ms

  近乎有序     | 冒泡排序   |    11,792,422 |       35,134 |    4.4 ms
  近乎有序     | 选择排序   |    12,497,500 |           10 |    2.6 ms
  近乎有序     | 插入排序   |        40,133 |       35,134 |    0.0 ms

这张表值得逐块读。

四、三个关键观察

观察 1：选择排序的比较次数永远是 $n^2/2$

看选择排序那一列比较次数：12,497,500 出现了四次，一模一样。

不管输入是随机的、已排序的、逆序的、还是近乎有序的。

原因：选择排序的内层循环必须扫描完右边的所有元素才能确定最小值。它没有"提前退出"的可能 —— 因为你没看完全部，就不知道有没有更小的。

这是一个很深刻的性质：选择排序的最好情况 = 最坏情况 = 平均情况。

1.3 节讲过"三种情况"的区分。而选择排序是个特例：它没有运气可言。

工程含义：如果输入数据可能被恶意构造，选择排序是"抗攻击"的 —— 因为对手没法让你变慢。而冒泡和插入在特定输入下会快得多的同时，在另一些输入下慢得多。

观察 2：插入排序在"近乎有序"时接近 $O(n)$

看最后一行：

算法	近乎有序时的比较次数	随机时的比较次数	加速比
冒泡排序	11,792,422	12,490,479	1.06 倍（几乎没用）
选择排序	12,497,500	12,497,500	1.0 倍（完全没用）
插入排序	40,133	6,162,995	154 倍！

插入排序只用了 4 万次比较 —— 而数据量是 5000。也就是说平均每个元素只往回比较了 8 次。

对比理论值：$n = 5000$ 时，完全有序只需要 $n - 1 = 4999$ 次比较。插入排序的 40,133 次，已经非常接近这个下界了。

冒泡排序这里有个反直觉的结果：它明明也做了"一整轮无交换就退出"的优化，为什么在近乎有序的输入上还是用了 1179 万次比较？

因为那个优化的条件是"一整轮完全没有交换" —— 而"近乎有序"的数据里有 10 对逆序，这 10 对分散在数组中，每一轮都会有交换发生，优化根本触发不了。

教训：一个优化只在特定条件下生效，而那个条件可能比你想的苛刻得多。插入排序的"提前退出"是每个元素独立的（发现位置对了就停），所以它对"局部有序"也能享受收益。

插入排序的这个性质在工程上极有价值。

现实世界的数据经常是"几乎有序"的：

已经排好序的列表里插入几条新记录

日志按时间追加（本来就基本有序）

数据库里索引列的增量更新

这就是为什么工业级的排序算法（比如 C# 的 Array.Sort）在小数组和近乎有序时会切换到插入排序。 8.5 节会详细讲这个。

观察 3：选择排序的移动次数极少

看"移动次数"那一列：

输入	选择排序的移动次数
随机	4,995
已排序	0
完全逆序	2,500
近乎有序	10

即使数据量是 5000，选择排序的移动次数也不超过 5000 —— 因为每轮最多交换一次，总共最多 $n-1$ 次。

（完全逆序时只有 2,500 次，因为前一半轮次交换完之后数组已经有序，后一半不需要再换。）

对比冒泡和插入：随机输入下它们都移动了 615 万次。

这个性质在什么时候有价值？

当"移动元素"的代价远高于"比较元素"时。

具体场景：

元素是很大的结构体（比如一个 1KB 的记录）—— 移动它要拷贝 1KB 内存，而比较可能只需要看其中一个字段

移动有副作用（比如移动触发写日志、或者对象有引用计数）

在这些场景下，选择排序反而是三种里最合适的 —— 虽然它比较次数最多，但移动次数是 $O(n)$ 而不是 $O(n^2)$。

这再次说明："比较次数少"和"更快"不是一回事。取决于哪个操作更贵。

五、三种排序的完整对比

	冒泡排序	选择排序	插入排序
最好情况	$O(n)$（已有序，带优化）	$O(n^2)$	$O(n)$（已有序）
最坏情况	$O(n^2)$	$O(n^2)$	$O(n^2)$
平均情况	$O(n^2)$	$O(n^2)$	$O(n^2)$
比较次数	随数据变化	恒为 $n^2/2$	随数据变化
移动次数	$O(n^2)$	$O(n)$	$O(n^2)$（但常数比冒泡小）
稳定性	稳定	不稳定	稳定
实际速度（随机）	最慢（6.3ms）	中等（3.1ms）	最快（1.6ms）
适用场景	教学	元素移动代价高	小数组、近乎有序

"稳定性"那一列是下一节的主题 —— 简单说：稳定意味着"值相同的元素，排序后保持原有相对顺序"。选择排序因为做"长距离交换"而破坏了这一点。

六、练习

练习 7.1.1（手写推演）对数组 [5, 2, 4, 1, 3]，手工推演冒泡排序的每一轮，列出每轮结束后的数组状态。 (a) 一共需要几轮？ (b) 总共发生多少次交换？ (c) 如果在第 2 轮结束后数组已经有序，第 3 轮会发生什么？

练习 7.1.2（计算）一个数组有 $n = 10{,}000$ 个元素。 (a) 选择排序的比较次数是多少？（精确值） (b) 选择排序最多移动多少次？ (c) 如果元素是 1KB 的结构体，比较只读其中一个 int 字段，估算一下"比较开销"和"移动开销"哪个大。

练习 7.1.3（判断）判断对错并说明理由： (a) 三个排序中最坏情况都是 $O(n^2)$，所以它们性能差不多。 (b) 插入排序在已排序的数组上是 $O(n)$，说明它比快速排序更好。 (c) 选择排序的比较次数固定，所以它是最"稳定"的排序算法。

练习 7.1.4（改进）冒泡排序有一个著名的改进：记录每一轮最后一次交换发生的位置，因为那个位置之后的所有元素都已经有序了，下一轮只需要扫描到那里为止。请说明这个优化在"近乎有序"的数据上能带来多大改善，并解释为什么。

练习 7.1.5（挑战·二分插入排序）插入排序里，"在左边已排序的部分找到插入位置"用的是线性扫描（从右往左一个个比）。既然左边那部分是有序的，为什么不用二分查找来定位？ (a) 这样能把比较次数降到多少？ (b) 这样做能让整个排序更快吗？为什么？ (c) 这个改进后的算法叫什么名字？

七、练习答案

7.1.1

数组 [5, 2, 4, 1, 3]：

第 1 轮（比较相邻元素，大的往后冒）：

比较	操作	数组状态
5 vs 2	交换	`[2, 5, 4, 1, 3]`
5 vs 4	交换	`[2, 4, 5, 1, 3]`
5 vs 1	交换	`[2, 4, 1, 5, 3]`
5 vs 3	交换	`[2, 4, 1, 3, 5]`

第 1 轮结束：[2, 4, 1, 3, 5] —— 最大的 5 冒到了最后 ✓

第 2 轮（最后一位已经确定，只比到倒数第二位）：

比较	操作	数组状态
2 vs 4	不动	`[2, 4, 1, 3, 5]`
4 vs 1	交换	`[2, 1, 4, 3, 5]`
4 vs 3	交换	`[2, 1, 3, 4, 5]`

第 2 轮结束：[2, 1, 3, 4, 5]

第 3 轮：

比较	操作	数组状态
2 vs 1	交换	`[1, 2, 3, 4, 5]`
2 vs 3	不动	`[1, 2, 3, 4, 5]`

第 3 轮结束：[1, 2, 3, 4, 5] —— 已经有序

第 4 轮：没有任何交换发生 → swapped 保持 false，提前退出。

(a) 实际执行了 3 轮（第 4 轮刚开始就退出了；如果数组一开始就完全有序，第 1 轮就会退出）。

严格说，最坏情况下需要 $n - 1 = 4$ 轮。本例中第 3 轮结束就已经有序，第 4 轮触发优化退出。

(b) 交换次数：4（第 1 轮）+ 2（第 2 轮）+ 1（第 3 轮）= 7 次。

(c) 第 3 轮结束后数组已经有序，第 4 轮会完整扫描一遍但不发生任何交换，然后 swapped 仍是 false，循环 break 退出。

注意：第 4 轮仍然要扫描一遍（$n-3$ 次比较）才能确定"没有交换"。这就是"提前退出"优化的局限 —— 它必须"多扫一轮"才能确认。

7.1.2

(a) 选择排序的比较次数是精确的：

$$\sum_{i=0}^{n-2}(n - 1 - i) = \frac{n(n-1)}{2} = \frac{10000 \times 9999}{2} = 49{,}995{,}000$$

约 5000 万次。

(b) 最多 $n - 1 = 9999$ 次交换（每轮最多交换一次）。

(c) 粗略估算：

操作	单次代价	次数	总代价
比较	读 2 个 int（8 字节），大概率在缓存里	5000 万次	约 400 MB 的内存读取量
移动	拷贝 1KB	约 5000 次（随机输入时约 $n$ 次）	约 5 MB 的内存写入量

移动的总开销远小于比较！ 差了将近 80 倍。

所以在这个场景下，选择排序反而可能是三个里最快的 —— 因为它的移动次数只有 $O(n)$，而冒泡和插入在随机输入下要移动 2500 万次 1KB 的结构体 = 25 GB 的内存拷贝。

这道题的核心是："哪种排序更快"取决于"比较"和"移动"哪个更贵。 在元素很大的时候，移动是瓶颈；在元素很小时（比如 int），比较是瓶颈。

7.1.3

(a) 错。 本节实测：随机输入下冒泡 6.3ms、选择 3.1ms、插入 1.6ms —— 最慢的是最快的 4 倍。近乎有序时差距更大（插入排序 0.0ms vs 冒泡 4.4ms）。

"都是 $O(n^2)$"只说对了增长趋势，没说常数。而常数差异可以到几倍甚至上百倍。
(b) 错。 两个问题：
1. 快速排序的平均复杂度是 $O(n \log n)$，当 $n$ 很大时远优于 $O(n)$ 吗？不 —— $O(n)$ 比 $O(n \log n)$ 更好。
2. 但前提是"数组已经有序"。如果数组是随机的，插入排序就退化到 $O(n^2)$，被快排远远甩开。
  
  正确说法：插入排序在已排序或近乎有序的输入上是 $O(n)$，这是它的特化优势，而不是普遍优势。
  
  实践中两者结合：快排在递归到小数组时切换成插入排序（见 8.5 节）。
(c) 错，混淆了两个概念。 "比较次数固定"说的是性能可预测；而"稳定"在排序里是一个专门术语，指"等值元素的相对顺序不变"。

而且讽刺的是：选择排序恰恰是三种里唯一不稳定的（下一节的主题）。

7.1.4

优化内容：记录每一轮最后一次交换的位置 lastSwap。因为 lastSwap 之后的所有元素在这一轮中都没有被交换过，说明它们已经有序。下一轮只需要扫描到 lastSwap 为止。

int end = n - 1;
while (end > 0)
{
    int lastSwap = 0;
    for (int j = 0; j < end; j++)
    {
        if (a[j] > a[j + 1])
        {
            (a[j], a[j + 1]) = (a[j + 1], a[j]);
            lastSwap = j;
        }
    }
    end = lastSwap;      // 下一轮只扫到这里
}

在"近乎有序"数据上的改善：巨大。

回到本节的实测数据：全部 10 对逆序分散在 5000 个元素中。普通的冒泡（只有 swapped 优化）：

每一轮都会在某个位置发生交换，所以 swapped 永远是 true
优化触发不了，要跑完 $n - 1$ 轮，总共 1179 万次比较

用了 lastSwap 之后：

每一轮结束后，end 会直接跳到最后一个逆序发生的位置
如果逆序集中在数组前半部分，end 会迅速收缩
最理想的情况下（只有 1 对相邻逆序），第一轮结束 end 就跳到那个位置，第二轮扫完就结束

能降到什么程度？

设逆序对涉及的最右位置是 $r$。那么：

第 1 轮扫描 $n$ 次，end 变成 $r$
第 2 轮扫描 $r$ 次，没有交换，end 变成 0，结束

总共 $n + r$ 次比较 —— 如果 $r$ 很小，就是 $O(n)$ 级别。

这个优化把冒泡排序从"几乎没用"变成了"在近乎有序时可用"。 但它仍然不如插入排序 —— 因为插入排序的"提前退出"是每个元素独立的，不需要一轮一轮地"试探"。

这又是一个"算法改进能否救回一个思路"的例子：优化能改善常数，但改变不了"冒泡必须一轮轮扫描"这个结构性劣势。

7.1.5

(a) 用二分查找定位插入位置，比较次数从 $O(n)$ 降到 $O(\log n)$。

整体比较次数从 $O(n^2)$ 降到 $O(n \log n)$。

(b) 不能。整体仍然是 $O(n^2)$。

原因：找到位置之后的"搬移元素"这一步没有变，仍然是 $O(n)$。

插入排序的两步：
  1. 找到插入位置     -> 可以用二分，O(log n)
  2. 把后面的元素腾开 -> 仍然要搬，O(n)    <- 瓶颈在这里

所以整体还是 $O(n^2)$，只是比较次数少了。

但如果"比较"比"移动"贵得多呢？ 那这个改进就有价值了。

实际收益通常很小，因为：

数组元素的移动是顺序内存访问，缓存友好，非常快

二分查找虽然比较次数少，但跳来跳去访问内存，缓存不友好

而且二分插入破坏了稳定性！（相等的元素可能被插到后面去）

所以工程上的排序库一般不用二分插入排序。

(c) 这个算法叫二分插入排序（Binary Insertion Sort）。

它最著名的应用是 java.util.Arrays.binarySort —— Java 在对小数组排序时用的就是它（不过 Java 的实现特意处理了稳定性问题）。

这个练习想说明的是：优化一个步骤，不一定能优化整体。 必须找到瓶颈在哪里 —— 插入排序的瓶颈是"移动"而不是"比较"。

这和 2.3 节讲的"用空间换时间"是同一类思考：先定位瓶颈，再优化。

八、常见错误

误区	纠正
认为"都是 $O(n^2)$ 所以差不多"	实测随机输入下最快的是最慢的 4 倍；近乎有序时插入排序比冒泡快 150 倍。
认为选择排序"最差"	它的比较次数确实是 $n^2/2$，但移动次数只有 $O(n)$。元素很大时它可能是最优的。
认为冒泡的 `swapped` 优化很有用	只在完全有序时有效。近乎有序（有零星逆序）时它触发不了 —— 实测仍有 1179 万次比较。
认为插入排序"慢"	它在近乎有序的输入上是 $O(n)$，是三种里唯一有实用价值的。工业级排序都用它处理小数组。
混淆"性能稳定"和"排序稳定"	"排序稳定"是专门术语，指等值元素保持原顺序。和"性能可预测"完全无关。
认为二分插入排序能到 $O(n \log n)$	比较降到 $O(n \log n)$，但移动仍是 $O(n^2)$，整体复杂度不变。

九、本节总结

三种 $O(n^2)$ 排序的"性格"完全不同，实测随机输入下耗时 6.3 / 3.1 / 1.6 ms。
选择排序的比较次数恒为 $n^2/2$，与输入完全无关 —— 它的最好 = 最坏 = 平均。
插入排序在近乎有序时接近 $O(n)$（实测 40,133 次比较 vs 随机的 616 万次，快 154 倍）。这是它最宝贵的性质。
冒泡的 swapped 优化只在"完全有序"时有效 —— 近乎有序时触发不了（实测仍有 1179 万次比较）。
选择排序的移动次数只有 $O(n)$（每轮最多一次交换）。当元素很大、移动代价高时，它反而可能是最优选择。
"比较次数少"不等于"更快" —— 取决于比较和移动哪个更贵。
二分插入排序能把比较降到 $O(n \log n)$，但整体仍是 $O(n^2)$ —— 因为移动才是瓶颈。

下一节衔接：本节末尾提了一句"选择排序是三种里唯一不稳定的"。那么"稳定"到底是什么意思？为什么它会影响排序的正确性（而不只是性能）？下一节用一个订单排序的例子说清楚。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "7.1",
  "title": "冒泡、选择、插入：三种 O(n^2) 排序",
  "covered": [
    "三种排序的扑克牌类比与完整实现",
    "四种输入下的实测对比（随机/已排序/逆序/近乎有序）",
    "选择排序比较次数恒定的性质与抗攻击性",
    "插入排序在近乎有序时接近 O(n)（快 154 倍）",
    "冒泡 swapped 优化在近乎有序时失效的原因",
    "选择排序移动次数为 O(n) 及其适用场景",
    "元素大小决定比较与移动谁更贵的分析",
    "二分插入排序（比较降到 O(n log n) 但整体不变）"
  ],
  "unresolved": [
    "稳定性留到 7.2",
    "逆序对与比较模型留到 7.3",
    "n log n 下界留到 7.4",
    "工业级排序（内省排序）留到 8.5"
  ],
  "canonical_terms": {
    "冒泡排序": "反复比较相邻元素并交换，每轮把最大值冒到末尾",
    "选择排序": "每轮选出最小值放到已排序部分末尾，比较次数恒定",
    "插入排序": "把当前元素插入左边已排序部分的正确位置",
    "比较次数": "排序过程中元素之间比较的总次数",
    "移动次数": "排序过程中元素被搬移的总次数"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 1.3 的最好/最坏/平均与 3.1 的数组交换",
    "读者能读懂 C# 的元组解构交换语法"
  ],
  "word_count_actual": 3060,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch07/Sec71/",
    "12 组（4 输入 × 3 算法）的比较/移动/耗时均为实测",
    "练习 7.1.1 的冒泡推演已手工验算（7 次交换）",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版说明写「选择排序移动次数为 n-1」与实测（逆序时 2500 次 = n/2）不符；原因是前一半轮次交换后数组已有序，后一半无需交换，已修正说明"
  ],
  "next": "7.2 稳定性：同分时谁在前"
}

7.1　冒泡、选择、插入：三种 O(n^2) 排序

第 7 章　基础排序与比较模型

7.1　冒泡、选择、插入：三种 $O(n^2)$ 排序

一、直觉：整理扑克牌的三种方式

二、三种实现

三、实测：四种输入下的巨大差异

四、三个关键观察

观察 1：选择排序的比较次数永远是 $n^2/2$

观察 2：插入排序在"近乎有序"时接近 $O(n)$

观察 3：选择排序的移动次数极少

五、三种排序的完整对比

六、练习

七、练习答案

八、常见错误

九、本节总结

results matching ""

No results matching ""

第 7 章 基础排序与比较模型

7.1 冒泡、选择、插入：三种 $O(n^2)$ 排序

一、直觉：整理扑克牌的三种方式

二、三种实现

三、实测：四种输入下的巨大差异

四、三个关键观察

观察 1：选择排序的比较次数永远是 $n^2/2$

观察 2：插入排序在"近乎有序"时接近 $O(n)$

观察 3：选择排序的移动次数极少

五、三种排序的完整对比

六、练习

七、练习答案

八、常见错误

九、本节总结

results matching ""

No results matching ""

第 7 章　基础排序与比较模型

7.1　冒泡、选择、插入：三种 $O(n^2)$ 排序