1. 排序算法比较表格
排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|---|
冒泡排序(BubbleSort) | O(N^2) | O(N^2) | O(1) | 是 |
选择排序(SelectionSort) | O(N^2) | O(N^2) | O(1) | 不是 |
插入排序(InsertionSort) | O(N^2) | O(N^2) | O(1) | 是 |
希尔排序(ShellSort) | O(N^(3/2)) | O(N^2) | O(1) | 不是 |
归并排序(MergeSort) | O(NlogN) | O(NlogN) | O(N) | 是 |
快速排序(QuickSort) | O(NlogN) | O(N^2) | O(logN) | 不是 |
堆排序(HeapSort) | O(NlogN) | O(NlogN) | O(1) | 不是 |
基数排序(RadixSort) | O (d(N+r)) | O (d(N+r)) | O(r) | 是 |
注意点
- 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
- 空间复杂度O(1)表示数组排序时,仅采用了一个额外的辅助单元进行数组元素的交换;O(N)一般表示采用了长度为N的辅助数组;
- 希尔排序的平均时间复杂度主要受到增量序列与数组长度的影响,当使用
h = h * 3 + 1
,如:1、4、13、40、121……时,平均时间复杂度为O(N^(3/2));当增量序列为1时,退化成插入排序,时间复杂度为O(N^2); - 当排序数组为降序而按升序排序时,快速排序退化成冒泡排序,时间复杂度为O(N^2);
- 快速排序使用原地排序的算法时,空间复杂度是O(1),真正耗空间的是递归调用。最优的情况下空间复杂度为O(logN),即每次切分都平分数组;最坏的情况下空间复杂度为O(N),即退化成冒泡排序的情况;
- 希尔排序是改进的插入排序,堆排序属于另一种形式的选择排序;
- 基数排序(radix sort):将记录的关键字看成是由d个关键字复合而成,每个关键字可能取r个值,则只要从最低位起,按关键字的不同值将记录“分配”到r个子序列,再按从小到大的顺序将各子序列依次首尾相接“收集”在一起,如此重复d趟(个位有序、十位有序、百位有序…),最终完成整个排序。这里的实现指的是计数基数排序,分为“分配”和“收集”两个过程:“分配”是对相应关键字的每种取值计数(即统计r个子序列的长度),确定每个子序列的起始位置;“收集”是根据各子序列的起始位置将记录复制到合适的位置。
基数排序示例:
引用自菜鸟教程
2. 速度测试
以下为对100个长度为10000的整型数组进行排序的测试,数据由0到100000中随机选取:1
2
3
4
5
6
7
8
9BubbleSort 耗费 17833 ms 经检查,测试数组全部有序
SelectionSort 耗费 3904 ms 经检查,测试数组全部有序
InsertionSort 耗费 4726 ms 经检查,测试数组全部有序
InsertionSortEX 耗费 2223 ms 经检查,测试数组全部有序
ShellSort 耗费 131 ms 经检查,测试数组全部有序
TopDownMergeSort 耗费 130 ms 经检查,测试数组全部有序
BottomUpMergeSort 耗费 112 ms 经检查,测试数组全部有序
QuickSort 耗费 107 ms 经检查,测试数组全部有序
HeapSort 耗费 115 ms 经检查,测试数组全部有序
说明:
- 测试使用的排序算法都是最原始的实现,希尔排序使用增量序列
h = h * 3 + 1
; - 原始的插入排序使用一一交换的方式把元素往后移动,为体现出与选择排序的差别,补充了现在一般的插入排序实现(InsertionSortEX),元素直接后移而不是一一交换;
- 归并排序有两种实现:自顶向下归并排序(TopDownMergeSort)和自底向上归并排序(BottomUpMergeSort)。自顶向下使用递归(化整为零),自底向上使用迭代(循序渐进)。显然,循环比递归快;
- 测试速度因环境不同而异。
3. 补充
最后附上其中七大排序算法(除了基数排序)的Java源码实现:Kanarien - Git Hub
Copyright © 2018, GDUT CSCW back-end Kanarien, All Rights Reserved