排序总结

内排序, 比较算法总结

排序方法	平均时间	最好时间	最差时间	空间复杂度	是否稳定
冒泡	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔	$O(n^{1.25})$,估计	-	-	$O(1)$	不稳定
快速	$O(n\log{n})$	$O(n\log{n})$	$O(n^2)$	$O(\log{n})$	不稳定
归并	$O(n\log{n})$	$O(n\log{n})$	$O(n\log{n})$	$O(n)$	稳定
堆	$O(n\log{n})$	$O(n\log{n})$	$O(n\log{n})$	$O(1)$	不稳定

内排序, 非比较算法总结

排序方法	平均时间	空间复杂度	是否稳定
计数排序	$O(n+k)$	$O(n+k)$	不稳定
桶排序	$O(n+C)$	$O(n+C)$	视桶内排序算法而定
基数排序	$O(d\cdot 2N)$	$O(N+M)$	稳定

计数排序

对输入是0到$k$之间的整数进行排序, 用于小范围的排序, 如0到100之间的排序. 由于计数排序不是比较排序, 排序的速度快于任何比较排序算法.

由于用来计数的数组C的长度取决于待排序数组中数据的范围.

桶排序

桶排序是计数排序的变种, 把计数排序中相邻的$m$个小桶放到一个大桶中. 在分完桶后, 对每个桶进行排序(例如快排), 然后合并成最后的结果.

桶排序假设序列由一个随机过程产生, 该过程将元素均匀而独立地分布在区间[0,1)上(即提前知道范围). 我们把区间[0,1)划分成n个相同大小的子区间, 称为桶. 将n个记录分布到各个桶中去. 如果有多于一个记录分到同一个桶中, 需要进行桶内排序. 最后依次把各个桶中的记录列出来记得到有序序列.

桶排序的平均时间复杂度为线性的$O(n+C)$, $C$为桶内快排的时间复杂度. 如果相对于同样的N, 桶数量M越大, 其效率越高， 最好的时间复杂度达到$O(N)$(即计数排序). 桶排序的空间复杂度为$O(N+M)$. 此外, 如果桶内的排序算法是稳定算法, 桶排序就是稳定的.

基数排序

基本思想为: 将待排数据中的每组关键字依次进行桶分配. 例子见下面的连接.

基数排序的性能比桶排序要略差, 每一次关键字的桶分配都需要$O(N)$的时间复杂度, 而且分配之后得到新的关键字序列又需要$O(N)$的时间复杂度(每一次的的关键字都有可能不同). 假如待排数据可以分为$d$个关键字, 则基数排序的时间复杂度将是$O(d\cdot 2N)$. 空间复杂度为$O(N+M)$, $M$为桶的数量.

另外, 基数排序是稳定的. 注意要保持稳定, 在桶分配完毕后, 对原数组的遍历需要从后向前进行.

关于非比较排序的资料参考:

• 计数排序、桶排序和基数排序

• 基数排序与桶排序，计数排序【详解】