排序Sorting

把元素按键或比较规则排成有序序列。选择时需要区分稳定性、额外空间、键的表示和输入是否已有序。

怎样选择#

具体算法	问题与前提	时间复杂度	辅助空间	选择与取舍
插入排序	小数组或近乎有序的输入	最坏 $O(n^{2})$ ，最好 $O(n)$	$O(1)$	稳定、原地；常用于混合排序的短区间。
归并排序	需要稳定排序或按顺序合并数据	$O(n \log n)$	数组归并 $O(n)$ ，另有 $O(\log n)$ 递归栈	时间界稳定；典型数组实现需要 O(n) 辅助空间。
快速排序	可随机访问、比较成本适中的内存数据	平均 $O(n \log n)$ ，最坏 $O(n^{2})$	普通递归期望 $O(\log n)$ ，最坏 $O(n)$	常见实现不稳定；枢轴、重复值和最坏情况保护需要一起考虑。
堆排序	额外空间有限且要求最坏时间保证	$O(n \log n)$	原地迭代实现 $O(1)$	原地实现额外空间 O(1)；通常不稳定。
计数排序	整数键的值域 k 不大	$O(n+k)$	稳定输出版 $O(n+k)$	可稳定实现；大值域会使计数数组得不偿失。
基数排序	键可拆成有限数位	$O(d(n+k))$	$O(n+k)$	LSD 方案每轮须稳定；还需计入键编码和辅助存储。
选择排序	更关心交换次数的小规模输入	$O(n^{2})$ 比较， $O(n)$ 交换	$O(1)$	常规实现原地但不稳定，大输入通常不选用。
冒泡排序	理解相邻交换与提前终止	最坏 $O(n^{2})$ ，提前退出时最好 $O(n)$	$O(1)$	主要用于基础教学，通常不用于工程中的通用排序。