排序算法怎么选：六种排序在同一批数据上的实测差别
同一批输入，六个页面各数一遍
本站每种排序都有一个单步演示台：左边改输入，点一次「前进」走一步，右边伪代码高亮当前行，变量面板同步显示 i、j、key，顶上的比较次数和移动次数跟着往上跳。要看出六种排序的差别，办法很笨但有效：把同一组 8 个数抄进六个演示的输入框，各自单步跑到结束，抄下最后的计数。下面两张表就是这么数出来的，均为 n=8、本站演示输入，单位是次。
| 输入特征 | 冒泡 | 插入 | 选择 | 归并 | 快排 | 堆 |
|---|---|---|---|---|---|---|
| 随机 8 个（默认） | 27 | 18 | 28 | 17 | 15 | 24 |
| 已经有序 | 7 | 7 | 28 | 12 | 28 | 27 |
| 完全逆序 | 28 | 28 | 28 | 12 | 28 | 24 |
| 基本有序（末位放 1） | 28 | 13 | 28 | 14 | 28 | 26 |
| 大量重复 | 28 | 21 | 28 | 14 | 18 | 27 |
| 全部相同 | 7 | 7 | 28 | 12 | 28 | 18 |
三条一眼能看出来的：选择排序六行全是 28，它的比较次数是 n(n−1)/2，n=8 时正好 28，与输入无关；已经有序时冒泡和插入各只比 7 次（n−1），选择和快排仍是 28 次；归并六行都在 12–17 之间，输入顺序几乎撼不动它。
再把这几份输入的移动/交换次数抄下来，「谁比得少、谁搬得多」就分出来了：
| 输入特征 | 冒泡 | 插入 | 选择 | 归并 | 快排 | 堆 |
|---|---|---|---|---|---|---|
| 随机 8 个 | 13 | 20 | 5 | 24 | 7 | 19 |
| 已经有序 | 0 | 7 | 0 | 24 | 0 | 22 |
| 基本有序（末位放 1） | 7 | 14 | 7 | 24 | 7 | 19 |
| 大量重复 | 16 | 23 | 4 | 24 | 9 | 18 |
| 全部相同 | 0 | 7 | 0 | 24 | 7 | 7 |
归并在本演示输入上恒定为 24 次移动，是六种里搬得最多的；选择排序最少，随机 5 次、重复 4 次、有序和全相同都是 0 次，代价是它的比较次数恒定 28。
六种各自的计数性格
冒泡一趟冒出一个最大值，相邻比较交换。已经有序时它只做 n−1 次比较就收工，这点和页面标注的最好 O(n) 对得上；平均与最坏都是 O(n²)，额外空间 O(1)，稳定。
插入把 key 插进前面已排好的那一段。有序时每个 key 比较一次就停，总共 n−1 次；完全逆序时第 i 个要挪 i 次。它的挪动次数等于逆序对个数，所以「基本有序」这类输入上非常快（本演示基本有序只比 13 次）。判断写成严格大于，相等时不越过，稳定。
选择每趟扫一遍找最小值与当前位交换，比较次数与输入无关，交换最多 n−1 次，是简单排序里换得最少的。远距离交换会打乱相等元素的次序，例如 [5, 5, 2] 第一轮就把前一个 5 换到了最后，不稳定。
归并最好、平均、最坏都是 O(n log n)，稳定，要 O(n) 额外空间。页面那句总结最准：运行时间几乎不受输入顺序影响，这是它和快速排序最大的区别。
快排平均比较约 1.39·n·log₂n，最坏 O(n²)。在本演示的划分方式下，已经有序和全部相同都会退化到 28 次，正好和列表最坏值吻合；随机选基准或三数取中可以避开。栈空间平均 O(log n)、最坏 O(n)，不稳定。
堆自底向上建堆总共 O(n)，之后 n−1 次取堆顶，每次下沉最多走 log₂n 层，全程在原数组里做，额外空间 O(1)，三种情况都是 O(n log 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) 最坏 | 否 |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
按数据特征怎么选
已经有序或基本有序，优先插入：本演示「基本有序」只要 13 次比较，比随机的 18 次还少，因为挪动次数就是逆序对个数。冒泡在严格有序时同样只有 7 次，但只要末尾掺一个 1，它就跳到 28 次。快排请避开这两类输入，本演示里已经有序和全部相同都落在 28 次的最坏情况上。
完全逆序时插入最吃亏（逆序对最多），本演示 28 次比较带最多的挪动；归并仍稳在 12 次，堆 24 次。大量重复时插入 21 次、归并 14 次、快排 18 次；如果重复到全部相同，插入和冒泡都降到 7 次，快排反而升到 28 次。
不知道输入长什么样、又在最坏情况上不能有闪失时，归并最省心（本演示 12–17 次），代价是 O(n) 空间；想原地解决就用堆，本演示 18–27 次，但它是 O(1) 空间。交换本身很贵（元素是整条记录、挪一次代价大）的场景，选选择排序：本演示换 0–7 次，换来 比较次数恒定 28。若值域有限，理论上计数排序可以做到 O(n+k) 且不靠比较，但本站没有这个演示，给不出可核的一手计数，这里不展开。
稳定性什么时候是硬要求
稳定是相等元素保持原有相对次序。六个里冒泡、插入、归并稳定，选择、快排、堆不稳定。硬要求的典型场合是多趟排序叠加：先按班级排、再按分数排，第二趟若不稳定，同分内部的班级次序就散了。选择排序的 [5, 5, 2] 就是活例子——第一轮远距离交换直接把两个 5 的先后颠倒了。
空间与常数开销的取舍
空间分三档：冒泡、插入、选择、堆是 O(1) 原地；归并要 O(n) 辅助数组，换来的是不受输入影响的稳定跑时；快排介于中间，平均 O(log n) 递归栈，最坏 O(n)。
常数上，n=8 这档输入真正决定步数的是每趟扫多长、每趟搬多少次，不是渐进记号——归并每趟都要往辅助数组搬（移动恒为 24），选择的比较恒定但可以几乎不换。这就是为什么值得亲手按一遍。
怎么自己在演示台试
先定一组 8 个数，在冒泡页跑到底，记下比较和移动两个计数；再把同一组数抄到另外五个页面各跑一遍，填成上面那两张表。然后换输入重来：升序、降序、升序但把 1 挪到末位、掺重复数字、八个全一样。每走几步就用「后退」回看，盯住计数器在哪一行跳变，问自己这一次比较为什么发生、那一次为什么省掉了。最后换一组数字再数一遍，验证你刚总结的规律是真规律，还是只在那一组数上碰巧成立。