排序算法时间复杂度,稳定性综合一览表
比较次数 |
交换次数 |
空间 |
类型 |
稳定性statble |
适用范围 |
|||||
最优 |
平均 |
最坏 |
最优 |
平均 |
最坏 |
|||||
冒泡排序 |
n(n-1)/2 |
n(n-1)/2 |
n(n-1)/2 |
0 |
n(n-1)/4 |
n(n-1)/2 |
O(1) |
基于比较排序交换 |
稳定 |
无任何实际使用范围;仅用于比较其他排序性能 |
插入排序 |
n-1 |
O(n^2) |
O(n^2) |
0 |
O(n^2) |
O(n^2) |
O(1) |
基于比较 |
稳定 |
当数据基本有序或者元素个数较少: |
二叉树排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(n) |
基于比较 |
不稳定 |
二叉树排序过程与快排等价,可分析快排性能 |
|||
选择排序 |
n(n-1)/2 |
n(n-1)/2 |
n(n-1)/2 |
0 |
O(n) |
O(n) |
O(1) |
基于比较 |
稳定 |
当比较的耗时,远小于交换的耗时. |
堆排序 |
O(nlogn |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
基于比较 |
不稳定 |
Top K问题:在一堆数据中选取前K(K>1)个数 |
归并排序Merge Sort |
O(nlogn |
O(nlogn) |
O(nlogn) |
O(1) |
O(nlogn) |
O(nlogn) |
O(N) |
基于比较 |
稳定 |
hadoop的reduce过程是一个归并过程(不是归并排序); |
原地归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
O(nlogn) |
O(nlogn) |
O(1) |
基于比较 |
稳定 |
最常见的是bottom up 归并 |
快速排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(1) |
O(nlogn) |
O(n^2) |
O(logn) |
基于比较 |
不稳定 |
|
最优 |
平均 |
最坏 |
||||||||
计数排序 |
O(n+2^k) |
O(n+2^k) |
O(n+2^k) |
O(n+2^k) |
非基于比较 |
稳定 |
||||
基数排序Radix Sort |
O(nk/s) |
O(nk/s) |
O(nk/s) |
O(n) |
非基于比较 |
稳定 |
在字符串中常见.基数排序中,需要使用到计数排序 |
|||
桶排序 |
O(n) |
O(nk) |
O(n^2k) |
O(nk) |
非基于比较 |
稳定 |
需要假定原始数据均匀分布于给定范围 |
另外:
-
锦标赛排序
锦标赛排序:是寻找第一和第二元素的最优比较次数的方法。 = N-1+logN,如果是要选择Top K元素,与heapsort基本无异,可以看成是heapsort的特例(较少次数比较的heapsort)
这个排序属于选择排序,因为每次都决定哪个元素需要和哪个比较或者交换,该算法思路可以扩展,如赛马问题:
赛马问题,是Top K问题的一个特例.
25匹赛马,5个跑道,也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的3匹马?
这里面,5个跑道,相当于5叉树,锦标赛排序,一次是比较2个元素,所以是2叉树。所以:基本思路是:5个,5个一组比较。
-
归并排序
归并排序可以用于求序列的”逆“。
交换、插入、选择,是比较排序的基本实现方式。交换:通过交换实现2个元素位置的正确性
插入:通过插入方式实现有序过程,因此数据是逐渐增加的过程。选择:是选择哪个元素进行比较或交者交换,在普通的选择排序中,可以不通过交换实现有序过程,比如构造空间O(n),原始序列不变的方式来实现。所以选择排序的一般实现虽然使用交换,但是并不属于基于交换方式的比较排序过程。
-
稳定与不稳定
稳定:稳定的排序是,总有一种实现方式使得对任意序列排序过程稳定。
不稳定:对于给定的排序算法的实现,总可以找到一个序列特例,其结果不稳定。
因此,快排,对case 1排序结果稳定,但并不说明快排是稳定的。
插入排序,如果实现方式中,每次比较<改成<=,这样,排序的结果是不稳定的,但这不能说,插入排序是不稳定的,是实现方式的问题,即,只要找到一种实现方式(用<号,而不是<=号)就可以实现稳定的排序。
-
原地排序
即使用原始序列进行排序,空间O(1),是衡量空间复杂度的。(注:总体来说,空间复杂度分析,要不时间复杂度分析难很多,而且空间限制通常比时间限制更难解决)。
-
排序的前提
传递性:a<b,b<c那么a<c
反自反性,a<b,那么!(b<a)
任意2个元素可比较
排序:是一个序列的“逆”的个数转换为0的过程。