十大排序算法的性能比较

排序算法经常在笔试和面试中考到，大部分会问平均时间复杂度、空间复杂度、稳定性和是否原地排序的性质，还有少部分会问到最优、最差时间复杂度，神烦无比。而网上的总结又五花八门、莫衷一是，因而自己也收集材料整理一番，虽然无法做到特别全面，但也希望能覆盖大部分的情况。

排序算法	平时时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度¹	原地排序	稳定性
选择排序²	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(1)$	原地	不稳定
冒泡排序	$\Omicron(n^2)$	$\Omicron(n)$	$\Omicron(n^2)$	$\Omicron(1)$	原地	稳定
插入排序	$\Omicron(n^2)$	$\Omicron(n)$	$\Omicron(n^2)$	$\Omicron(1)$	原地	稳定
希尔排序³	-	-	-	$\Omicron(1)$	原地	不稳定
快速排序	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n^2)$	$\Omicron(1)$	原地	不稳定
归并排序⁴	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n)$	非原地	稳定
堆排序⁵	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(1)$	原地	不稳定
计数排序⁶	$\Omicron(n+k)$	$\Omicron(n+k)$	$\Omicron(n+k)$	$\Omicron(n+k)$	非原地	稳定
桶排序⁷	$\Omicron(n+k)$	$\Omicron(n+k)$	$\Omicron(n^2)$	$\Omicron(n+k)$	非原地	稳定
基数排序⁸	$\Omicron(mn)$	$\Omicron(mn)$	$\Omicron(mn)$	$\Omicron(n)$	非原地	稳定

注释：

这里的空间复杂度并没有讨论递归的栈空间，否则快速排序的空间复杂度为 $\Omicron(\log(n))$
选择排序由于需要交换数组元素导致不稳定，若是链表排序，则不存在交换问题，因此会是稳定的
希尔排序的复杂度与间距序列的选取有关，由于各处的说法并不统一，因此未列出
归并排序可以用于链表的排序，同时可以递归的排序，也可以从下往上排序。对链表来说，自下而上排序不需要额外的栈空间和辅助空间。表中列出的是最常见的对数组的递归排序， $\Omicron(n)$ 的空间复杂度是由于引入了辅助数组
堆排序使用数组表达
计数排序中， $n$ 为元素数量， $k$ 为数据范围（或者说是映射后的数据范围），引入了前缀和计数数组和辅助数组（非原地排序），因此的空间复杂度 $\Omicron(n+k)$
桶排序的时间复杂度为 $\Omicron(n + n^2/k + k)$ ，当 $k \approx n$ 时有 $\Omicron(n + k)$ ，当 $k \approx 1$ 时有 $\Omicron(n^2)$
基数排序， $m$ 为数字的位数（关键字数量）， $k$ 为不同数字的个数（关键字值域）。表中数据是 LSD + 计数排序对数字排序的场景，则空间复杂度由 $\Omicron(n+k)$ 简化到 $\Omicron(n)$

目录