排序

排序是把一组元素按键值大小重排成有序序列的操作。常见基于比较的算法在平均与最坏时间、额外空间、是否稳定以及适用容器（数组还是链表）上各有取舍；面试里既要能讲清思路与复杂度，也要能手写归并、快排等核心实现。下面先给出常见算法对比，再按分类展开。

稳定性与比较排序基础

若两个键相等的对象在排序输出中与输入数据集中的顺序相同，则称该排序算法是稳定的（常见面试题：「快排是稳定的吗？」——标准实现不是）。

快速判断时盯住 相等键 会不会被交换，或 一次移动跨越多个位置？若是，相对顺序就可能被打乱，算法 不稳定。

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	$O (n^{2})$	$O (n)$	$O (n^{2})$	$O (1)$	原地	稳定
选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	原地	不稳定
插入排序	$O (n^{2})$	$O (n)$	$O (n^{2})$	$O (1)$	原地	稳定
希尔排序	$O (n lo g n)$ ~ $O (n^{3/2})$	$O (n lo g n)$	$O (n^{2})$	$O (1)$	原地	不稳定
归并排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	非原地	稳定
快速排序	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	$O (lo g n)$	原地	不稳定
堆排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	原地	不稳定
计数排序	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (n + k)$	非原地	稳定
桶排序	$O (n + k)$	$O (n + k)$	$O (n^{2})$	$O (n + k)$	非原地	稳定
基数排序	$O (n \times k)$	$O (n \times k)$	$O (n \times k)$	$O (n + k)$	非原地	稳定

表中 $k$ 表示键值范围或位数等辅助参数；「原地」指额外空间为常数级（不含输入本身），「非原地」通常需要与 $n$ 或 $k$ 相关的辅助空间。