Olverae Assets

1 一句话定义

排序（sorting）就是把一组数据按某个顺序（通常是从小到大）重新排列；不同排序算法做的事一样，但快慢、是否稳定、要不要额外空间各不相同——这一页教你怎么选。

把它想成整理手里的扑克牌：有人每次抽一张插到合适位置（插入排序），有人每轮挑出最小的一张摆到最左（选择排序），有人把相邻两张比一比、大的往右挤（冒泡排序）。结果都是排好序，但花的功夫差很多。这一页让这几种"整牌手法"同台赛跑，你来挑最合适的那种。

排序的目标永远一样：把柱子从矮到高排好。难点不在"会不会排"，而在用哪种算法——下一节让 5 种算法在同一组数据上赛跑，亲眼看谁的"比较次数"少。

2 模型 · 看着柱子排 + 5 种同台赛跑

先选一种算法单步看它怎么搬柱子（琥珀=正在比较，紫=正在交换，绿=已就位）；再点 全部赛跑，让 5 种算法在同一组数据上比"比较 / 交换"次数——这就是选型的依据。

排序可视化

当前算法代码

0

比较次数

0

交换/移动

提示

选一种算法，点 ▶ 看柱子怎么排；或点下面的「全部赛跑」直接比快慢。

绿色行 = 比较次数最少的赢家。数据 = 上面这 8 个柱子。

3 核心要点 · 一张表 + 3 个关键词定生死

母页的命根子就是下面这张对照表和三个关键词：复杂度（快不快）、稳定（相等元素会不会被打乱）、原地（要不要额外开数组）。考试最爱"黑盒识别 + 问稳定性"。

算法	最好	平均	最坏	额外空间	稳定	一句话特点
冒泡 Bubble	O(n)	O(n²)	O(n²)	O(1)	稳定	相邻比较、大的右移；加 swapped 可对"已排好"提前收工
选择 Selection	O(n²)	O(n²)	O(n²)	O(1)	不稳定	每轮选最小换到前面；交换次数最少，但比较恒为 O(n²)
插入 Insertion	O(n)	O(n²)	O(n²)	O(1)	稳定	把每张牌插到左边有序区；数据基本有序时极快（接近 O(n)）
归并 Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	分治：拆到底再两两合并；快且稳定，但要 O(n) 额外数组
快排 Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定	选基准 partition；平均最快，但最坏会退化 O(n²)

① "稳定"到底稳的是什么

一句话：稳定 = 值相等的元素，排完后相对前后顺序不变。当你按"次要键"二次排序时，这点至关重要。

比如先按姓名排好，再按班级稳定排序，同班的人就还保持原来的姓名顺序。冒泡 / 插入 / 归并稳定；选择 / 快排因为会"远距离交换"而不稳定。

原序: (1,a)(1,b) 稳定: (1,a)(1,b) ← a 仍在 b 前不稳定:(1,b)(1,a) ← 被打乱了

② O(n²) 三人组 vs O(n log n) 两人组

一句话：冒泡/选择/插入是 O(n²)，数据一大就慢；归并/快排是 O(n log n)，大数据首选。赛跑里你会看到比较次数差出一截。

n=10 时差别不明显，n=10000 时 O(n²) 要 ~1 亿次、O(n log n) 只要 ~13 万次。这就是为什么标准库的 sort 都用 O(n log n) 级别的算法。

③ 选型口诀

一句话：小数据/基本有序 → 插入；要稳定又要快 → 归并；一般大数据 → 快排；省内存且只挑几个最值 → 选择/堆。

插入：n 小或几乎有序时反而最快、还稳定。归并：稳定 + 最坏也 O(n log n)，代价是 O(n) 空间。快排：平均最快、原地，但要防最坏退化（随机基准）。

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是手写排序最常翻车的坑——边界越界、把"稳定"写没了、找最小写漏、只比一次插不到位。点击卡片看运行效果。

① 冒泡内层越界

j < n（漏了 -1）→ 读到 a[n] 越界

② 把稳定写没了

比较用 >= 而非 > → 相等也交换，破坏稳定

③ 选择排序漏更新 min

找到更小的却没记下下标 → 根本没排序

④ 插入用 if 不用 while

只往前比一次 → key 插不到正确位置

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题正对着考试套路：黑盒识别算法、稳定性、复杂度、选型、额外空间。点错也别灰心，提示会讲清楚。最后到练习系统亲手写排序。

去做例题：排序 · 升序排序

去做例题

Sorting Algorithms

排序对比与选型