Sorting Algorithms Summary

Time/space/stability cheatsheet and selection guidance

#algorithm #concept #growing #sort

[!info] related notes 算法面试题型 MOC 分治递归算法

排序算法总结

稳定性（Stability）

稳定排序：相等元素的相对顺序在排序后保持不变。

例：按成绩排序学生，(Alice, 90) 和 (Bob, 90)，稳定排序保证 Alice 仍在 Bob 前面。

不稳定排序（选择排序、快排、堆排）可能交换相等元素的顺序。需要稳定时可添加辅助 key（如原始下标）。

速查表

排序算法	时间复杂度	额外空间	稳定
选择排序	$O(n^2)$	$O(1)$	否
冒泡排序	$O(n^2)$	$O(1)$	是
插入排序	$O(n^2)$	$O(1)$	是
归并排序	$O(n \log n)$	$O(n)$	是
快速排序	平均 $O(n \log n)$，最坏 $O(n^2)$	$O(\log n)$ 栈	否
堆排序	$O(n \log n)$	$O(1)$	否
计数排序	$O(n + m)$	$O(m)$	是
基数排序（LSD）	$O(n \times d)$	$O(n + \text{base})$	是

关键排序可视化

归并排序

[38, 27, 43, 3, 9, 82, 10]
         拆分
[38,27,43,3] [9,82,10]
[38,27] [43,3] [9,82] [10]
[38][27] [43][3] [9][82] [10]
         合并（有序合并）
[27,38] [3,43] [9,82] [10]
[3,27,38,43] [9,10,82]
[3,9,10,27,38,43,82]

核心：合并两个已排序子数组，每步比较首元素，$O(n)$ 完成合并。

快速排序

[3, 6, 8, 10, 1, 2, 1]
选 pivot = 6
分区：[3,1,2,1] [6] [8,10]
递归排序左右两部分
[1,1,2,3] [6] [8,10]
→ [1,1,2,3,6,8,10]

核心：partition 操作将数组分为 < pivot 和 > pivot 两部分。

堆排序

建大顶堆：O(n)
依次取堆顶（最大值）放到末尾，调整堆：O(n log n)

选择建议

小数组（n < 50）：插入排序，常数因子小，实际最快。
通用场景、不需稳定：随机化快排，缓存友好，平均最快。
需要稳定、可承受额外空间：归并排序。
需要 $O(1)$ 额外空间、不需稳定：堆排序。
整数 key 且范围可控：计数排序 / 基数排序，突破 $O(n \log n)$ 下界。

面试要点

手写快排：partition 的写法（Lomuto vs Hoare），边界处理。
归并排序应用：逆序对计数、区间统计等在 merge 阶段附加操作的变体。
堆排序：理解 heapify 的 $O(n)$ 建堆过程。
稳定性：能举例说明哪些排序稳定、哪些不稳定，以及何时需要稳定。
比较排序下界：$O(n \log n)$，基于决策树模型证明。