袋鼠知识库

主题

常见排序算法图解 ​

1. 为什么要单独做一页图解 ​

很多人学排序时的问题，不是代码不会写，而是“过程感”太弱。知道时间复杂度是一回事，真正看懂元素在每一轮比较、交换、划分、合并里怎样变化，是另一回事。

这一页专门解决这个问题。写法上不再强调“全量定义”，而是强调：

  1. 这个算法每一轮到底在做什么。
  2. 元素移动的方向和原因是什么。
  3. 为什么它最后一定会有序。
  4. 复杂度和稳定性是如何从过程里长出来的。

2. 先建立一张总表 ​

算法核心思想平均复杂度稳定性原地
冒泡排序相邻比较，大数后沉O(n^2)稳定是
选择排序每轮选最小值放前面O(n^2)不稳定是
插入排序把当前元素插入已排序区O(n^2)稳定是
归并排序分治拆分，再有序合并O(n log n)稳定否
快速排序选基准做划分O(n log n)不稳定近似原地
堆排序维护堆顶最值O(n log n)不稳定是

下面的图解会分成两组：

  1. 比较排序：重点看元素之间怎样比较、交换、划分、合并。
  2. 非比较排序与改良排序：重点看怎样利用值域、位数、分桶或分组结构跳出纯比较模型。

3. 冒泡排序 ​

3.1 它到底在做什么 ​

3.2 动态图 ​

3.3 过程理解 ​

3.4 Go 实现 ​

3.5 它为什么稳定 ​

4. 选择排序 ​

4.1 它和冒泡的本质区别 ​

4.2 Go 实现 ​

4.3 为什么它通常不稳定 ​

5. 插入排序 ​

5.1 它的思维方式最像“整理手里的扑克牌” ​

5.2 动态图 ​

5.3 过程理解 ​

5.4 Go 实现 ​

5.5 为什么它稳定 ​

6. 归并排序 ​

6.1 它最重要的不是“拆”，而是“合并时保持有序” ​

6.2 动态图 ​

6.3 过程理解 ​

6.4 Go 实现 ​

6.5 为什么它稳定 ​

7. 快速排序 ​

7.1 快速排序的核心不是交换，而是划分 ​

7.2 动态图 ​

7.3 过程理解 ​

7.4 Go 实现 ​

7.5 为什么它平均快，但最坏会退化 ​

8. 堆排序 ​

8.1 它的关键不是“比较”，而是“不断把堆顶最值拿出来” ​

8.2 动态图 ​

8.3 Go 实现 ​

8.4 堆排序适合怎样理解 ​

9. 希尔排序 ​

9.1 它为什么是“改良版插入排序” ​

9.2 过程理解 ​

9.3 Go 实现 ​

9.4 适合怎么记 ​

10. 计数排序 ​

10.1 它为什么不靠比较 ​

10.2 过程理解 ​

10.3 Go 实现 ​

10.4 什么时候适合 ​

11. 桶排序 ​

11.1 它的核心不是“排”，而是“先分布，再局部处理” ​

11.2 过程理解 ​

11.3 Go 实现 ​

11.4 什么时候适合 ​

12. 基数排序 ​

12.1 它为什么要“按位排” ​

12.2 过程理解 ​

12.3 Go 实现 ​

12.4 什么时候适合 ​

13. 什么时候该选哪一种 ​

14. 最容易混淆的几组区别 ​

10.1 冒泡 vs 选择 ​

10.2 插入 vs 选择 ​

10.3 归并 vs 快速 ​

10.4 快速 vs 堆 ​

15. 学这一页时应达到的标准 ​

16. 对比版补充 ​