五种排序算法交互实验
桌上摆着一排写有数字的卡片：8、3、5、1、9、2。目标很简单，让它们从小到大排列。
你可以从左到右，不断把较大的数字往右推；也可以每次找出最小的数字，放到队伍前面；还可以像整理扑克牌一样，把新拿到的一张插进已经排好的手牌里。目标相同，整理的思路却很不同。
这次沿用迷宫与地牢实验室的形式，做一个可以亲手改参数的排序 Demo。它由浏览器根据当前数据计算每一步，支持自定义数字、暂停、单步回看和反复运行。先观察数字怎么移动，再理解为什么这样做能排好。
动手体验排序
下面的实验可以直接操作。点击“实验参数”展开设置，选择一种初始排列，或者输入自己的数字，再点击“开始运行”。
| 想观察什么 | 怎么操作 |
|---|---|
| 每一步在做什么 | 先用 4–8 个数字，点击“下一步”；点“上一步”或拖动进度条可以回看 |
| 不同算法如何处理同一组数据 | 直接切换上方算法卡片，原始数字与顺序保持不变 |
| 数据规模带来的差别 | 调整“数据数量”，范围为 4–32 个 |
| 输入本来就很整齐会怎样 | 初始排列选择“已排序”或“接近有序” |
| 最糟糕的排列会怎样 | 选择“完全逆序”，再对照冒泡与插入 |
| 相同数字会不会换前后顺序 | 选择“大量重复值”，或输入 4, 4, 1 |
| 快排的基准为什么重要 | 切到快速排序，分别选中间位置、末尾位置或由种子随机选取 |
| 不想等到演示结束 | 点击“看结果”，或展开“同组数据，五种算法一起对照” |
“重跑同一组”从同一份原始数据重新运行；“换一组”更换随机种子并生成新数据。切换算法、调整数量或选择排列时，演示会回到第 0 步，等待你开始。种子和手动输入的数字需要点击“用这些参数生成”确认。自定义支持 2–32 个 1–99 的整数，用空格或逗号分隔。
生成数据时，普通排列使用不同的数，“大量重复值”则从 20、40、60、80 中抽取。保持数量和种子相同，在随机、已排序、逆序与接近有序之间切换，可以比较同一批数的不同排列。接近有序通过对有序数据做少量相邻交换得到。
柱子的高度表示数值，底部的 #1、#2…… 表示它最初在输入中的位置。黄框表示正在比较或移动的数字，紫色标记当前关注项，绿柱表示已经到达最终位置。青色虚线框表示这一小段有序，其中的数字之后仍可能移动。
这一区分很有用：插入排序左边的一叠牌虽然已整理好，新来的小牌还是可能插到最前面。
冒泡排序：相邻交换
想象一排气泡，相邻的两个要比一下大小。如果左边更大，就交换。大的那个因此向右走了一格，接着与下一个比较。
例如 5、2、4、1 的第一轮：
1 | 5 2 4 1 比较 5 和 2，交换 |
一轮过后，未排序区域中的最大值一定来到右端。 下一轮不必再看它，继续处理左边剩下的数字。演示里，右侧的绿柱会逐渐增多。
这里还加了一个容易理解的判断：如果整轮都没有发生交换，说明相邻数字已经按顺序排列，可以直接停下。因此，本页冒泡排序遇到已排序数组时只需一轮。这个带提前退出的规则也见于 NIST 的冒泡排序说明。
试一试： 用 8 个已排序数字运行冒泡。它会比较 7 次，交换 0 次；改成完全逆序后，就能看到大量相邻交换。冒泡的局限也在这里：一个很小的数如果落在最右边，往往要经历多轮，才能慢慢回到前面。
选择排序：寻找最小值
如果要让一队人按身高排列，可以先扫一眼所有人，找到最矮的，让他站到队首；然后在剩下的人里继续找最矮的。
选择排序每轮做两件事：先找，后换。 扫描过程中只更新“目前见过的最小值”，直到整段看完，才把它与本轮队首交换。
同样是 5、2、4、1：
1 | 5 2 4 1 扫描全部，发现最小值是 1 |
只交换一次，就把 1 放到了最终位置。演示中的紫色候选会在扫描时改变，左侧绿柱则一轮增加一根。《Algorithms, 4th Edition》的选择排序介绍
它的代价是：即使输入已经排好，每轮仍要扫描剩余区域。 本页对 n 个数字进行 n(n−1)/2 次数值比较；但跳过了自己与自己的交换，真正的交换最多 n−1 次。
试一试： 打开 8 个已排序数字的选择排序，点击“看结果”。比较次数是 28，交换仍是 0。和冒泡的 7 次比较对照，就能发现：“不移动”不等于“没做多少检查”。
插入排序：逐个归位
整理手牌时，我们通常不会把所有牌反复打乱。左手先拿着一叠有序的牌，每拿到一张新牌，就从右往左找位置，插进去。
插入排序也是如此：左边维持有序，右边等待处理。假设左侧已有 2、5、8，新来的数字是 4：
1 | 2 5 8 [4] 4 比 8 小，向左挪 |
方括号标出正在插入的 4。插入结束后，前四项已经有序，但它们还未必处于整组数据中的最终位置。这正是 Demo 使用青色虚线框，而没有提前把它们涂绿的原因。
本页采用相邻交换来表现插入，便于跟踪同一张卡片。常见的另一种写法会先暂存新牌，把较大的元素依次右移，再将新牌写入空位；两者整理思路一致，数组写入次数有所不同。《Algorithms, 4th Edition》的插入排序介绍
试一试： 把初始排列设为接近有序，再改成完全逆序。前一种情况下，大部分数字很快就能找到位置；后一种情况下，新数字经常要一路挪到最左端。插入排序是否轻松，和原始数据离“排好”有多远关系很大。
归并排序：拆分与合并
面对一大堆数字，可以先把任务拆小：分成两半，每半继续分，直到每组只有一个数字。一个数字天然有序，接下来就能逐层合并。
合并的关键是：两边都已经有序，所以只需比较各自的队首。 较小的先进入新队列，再看这一边新的队首。
例如合并 2、5、8 和 1、4、9：
1 | 左队 右队 临时队列 |
Demo 下方会出现一条临时队列。它逐项接收数字，装好后回填原区间；为了看清合并结果，一整段回填被展示为一个步骤，但统计中仍按实际回填的元素数计算写入。
每一层合并总共处理约 n 个元素，拆分层数约为 log₂ n，所以常规归并排序的时间量级是 O(n log n)。本页使用数组临时队列，需要 O(n) 额外空间，相等时优先取左侧元素。《Algorithms, 4th Edition》的归并排序说明
试一试： 打开归并排序，展开“跟着算法步骤看”。注意先完成的是一小段的合并，随后才合并更大的区间。它的交换次数始终为 0，但临时队列和回填产生了数组写入，说明“交换少”不能单独代表“工作少”。
快速排序：按基准分组
快速排序也会拆分任务，但拆分方式不同：先挑一个数字作为基准，把更小的放在一边，其余放在另一边，然后分别处理这两边。
本页演示的规则是：先把基准移到当前区间末尾，接着从左到右扫描。遇到小于基准的数字，就把它放进左侧的“小于组”；扫描结束后，再让基准站到两组之间。这叫 Lomuto 分区。
1 | 小于基准的一组 | 基准 | 大于或等于基准的一组 |
基准就位了，不代表左右两边内部已经排好。 两侧还要按同样规则继续处理。演示里，基准变绿后会留在原地，其他区间继续变化。
快排很依赖分组是否均衡。大致对半分时，需要处理的层数较少；如果每次一边没有元素，另一边几乎还是原来那么长，就会反复扫描大区间。它通常讨论的平均时间是 O(n log n)，最坏情况仍可达 O(n²)，具体表现取决于输入和分区实现。《Algorithms, 4th Edition》的快排分析
试一试： 用 12 个已排序数字，末尾元素作基准。最大的数每次都落在区间末尾，一侧始终为空，数值比较为 11 + 10 + … + 1 = 66 次。再把基准改成“中间位置的元素”，看看分区和比较次数怎样变化。
这里说的是位置居中，并没有提前寻找数值中位数。第三个选项“由种子随机选取”则使用可复现的随机序列挑基准，也不是一定能避开最坏情况。
还可以试试大量重复值。本 Demo 使用严格“小于基准”的二路分区，相等项都留在另一侧：如果所有数字一样，仍会退化。这也说明，谈快排表现时，需要知道使用的是哪一种实现；处理大量重复值时，三路分区会有不同表现，本页没有把它与二路分区混在一起。
排序的稳定性
如果只看数值，两个 4 没有区别。但如果它们代表两条订单，原始先后顺序可能有意义。
稳定排序指：按当前关键字排序后，关键字相等的记录仍保持原来的相对次序。它不要求所有元素都不动，也不是“每次执行得到一样的答案”。
在 Demo 的“自定义数字”里输入 4, 4, 1。两个 4 分别标为 #1 和 #2：
1 | 原始数据：4#1 4#2 1#3 |
选择排序第一轮将最小的 1 与队首交换，原先在前的 4#1 被送到后面，两个 4 的顺序反转。这就是本页选择排序不稳定的一个反例。
冒泡只在左边严格大于右边时交换；插入不会越过相等的前项；归并在相等时先取左队。这里的这三种实现都保留相等记录的先后顺序。选择排序和本页快排则不保证这一点。
直接载入这组三个数字 → 切换算法后看柱底编号，比只看柱高更容易理解稳定性。
五种算法对比
下表对应本文采用的常规实现。n 是元素个数，“额外空间”不包含输入数组；快排一栏计入递归调用栈。归并没有加入“已排序区间直接跳过合并”的优化。
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡（含提前退出） | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速 | O(n log n) | O(n log n) | O(n²) | 平均 O(log n)，最坏 O(n) | 不稳定 |
这些量级可以结合 Princeton 的排序资料、归并分析、快排分析和 NIST 的冒泡说明阅读。快排的平均表现通常基于随机排列或随机基准等假设，不能理解成“任意数据都保证这么快”。
不熟悉大 O 也没关系。先把它看作“当数字越来越多，工作量大致怎样增长”：O(n²) 的增长通常比 O(n log n) 更陡。它描述增长趋势，不是精确秒数，也不保证较小数组上的胜负。
实验下方的对照表使用完全相同的原始数据，分别计算五种算法的最终操作次数。它能帮助你检验刚才的观察，但要分清三个指标：
- 数值比较：判断两个排序数值的大小；不统计循环下标、边界检查等条件。
- 交换：两项互换位置；自己和自己不算一次交换。
- 数组写入：一次交换记为 2 次写入；归并还包含临时队列与回填。用于回放的快照复制不计入其中。
不同算法每一“演示步”包含的工作并不相同。归并回填一整段算一个展示步骤，冒泡的一次比较和一次交换则分开显示。因此，播放速度、演示步数和看完花了多久，都不能当成算法的实际运行耗时。 为了支持拖动回看，Demo 还会保存过程快照；这部分是演示器的开销，不是表格里的排序算法空间需求。
三个练习
- 先预测，再查看结果。 用 8 个已排序数字，猜冒泡、选择和插入分别会比较多少次，再展开对照表。这里会得到 7、28、7。
- 只改一个条件。 固定快排的数量、种子和已排序输入，只把基准从末尾改为中间位置，观察每次分区是不是更均衡。
- 寻找一个反例。 输入
4, 4, 1，先判断哪种算法会保留两个 4 的先后次序，再用柱底编号核对。
发现有意思的过程，可以点击“分享”保存当前算法、种子与数据条件。别人打开后会从第 0 步开始，能够再次运行。相同版本与参数可以复现；如果分享自定义数据，这些数字也会包含在链接里。
排序的乐趣在于，几条简单规则就能产生截然不同的过程。下次面对一排数字，可以先想一想：是让它们相邻交换，先找出最小值，把新项插入有序区，合并两队，还是先用一个基准分成两边？然后把这个猜想放进实验室，亲手验证。