排序算法动画
这里有八种排序算法的交互动画：冒泡、选择、插入、归并、快速、堆、计数和基数排序。前六种通过比较元素确定顺序；计数排序统计键值，基数排序按数位分桶。你可以修改输入，逐步查看动画与对应代码。
所有课程都解决同一个问题：把数组排成有序序列。不同之处是策略。对照它们的比较、移动和空间开销，可以理解稳定性、原地排序、自适应性与最坏情况。
怎样观察排序算法
打开一门课，修改输入，再播放或单步执行。重点看四件事：
- 怎样确定顺序：冒泡排序比较邻居，选择排序寻找整个未排序部分的最小值，归并排序比较两个有序序列的头部。计数排序和基数排序不逐对比较元素。
- 是否稳定：两个值相等时，原顺序是否保留？稳定排序会让
12a仍排在12b前面。按多个字段排序记录时，这个性质很有用。 - 是否原地排序：额外空间是 O(1)，还是需要另一个数组？归并排序用缓冲区换取 O(n log n) 的时间保证；堆排序通过堆结构实现原地排序。
- 最坏情况是什么：快速排序可能退化到 O(n²)，归并排序则保持 O(n log n)。平均表现相近的算法，最坏表现也可能不同。
排序算法复杂度对比
冒泡、选择和插入排序的平均时间复杂度为 O(n²)。归并、快速和堆排序的平均时间复杂度为 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 log n)§ | O(n log n) | O(n log n) | O(1) | 否 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 是 |
| 基数排序 | O(d·n)‡ | O(d·n) | O(d·n) | O(n + b) | 是 |
* 冒泡排序的 O(n) 最好情况指带提前结束检查的优化版。经典版仍执行全部轮次。插入排序在已有序输入上也达到 O(n)，选择排序则仍需扫描剩余部分。
† 快速排序的 O(log n) 空间指平均递归栈深度；分区持续失衡时，递归栈可能达到 O(n)。
‡ k 是键值范围，d 是最大键值的位数，b 是基数。固定基数时，基数排序的时间写作 O(d·n)；把基数也作为变量时，每轮还要处理桶，时间为 O(d·(n + b))。这些参数决定了非比较排序何时合适。
§ 堆排序这一行是时间上界。父节点不小于子节点时下沉就会停止，所以并非每组输入都做同样多的工作；元素全部相等时只需线性时间。
建议的学习顺序
从冒泡排序开始，看清相邻交换如何产生平方级的比较次数。接着学选择排序：它减少写入，每轮最多交换一次，却无法利用已有顺序。再学插入排序，观察有序前缀怎样扩展，以及接近有序的输入为何需要较少移位。
随后学习三种平均 O(n log n) 的比较排序。归并排序先拆分，再合并有序序列，需要 O(n) 缓冲区。快速排序通过分区把轴值放到合适位置；分区是否均衡影响后续工作量。堆排序利用堆选出当前最大值，在原数组内完成排序，也把排序与数据结构联系起来。
最后看不依赖逐对比较的两种算法。计数排序把键值当下标，统计次数，用前缀和计算位置，再写入输出数组。基数排序逐位执行稳定分配，把当前位的顺序与先前各位的顺序组合起来。这里也能看出稳定性如何成为算法正确性的条件。
全部排序课程
选择下方课程，修改输入或单步执行，查看动画与代码。