原本还打算写希尔排序和堆排序呢,不过由于时间原因也只能写这些排序了。下面总结和对比一下常用的排序方法吧。
1. 排序方式 #
插入排序:直接插入排序,二分插入排序,表插入排序,希尔插入排序;选择排序:直接选择排序,树形选择排序,堆排序;交换排序:冒泡排序,快速排序。还有归并排序、基数排序,等等。
2. 稳定性 #
稳定的:冒泡排序,双向冒泡排序(鸡尾酒排序),插入排序,计数排序,归并排序,二叉排序树排序,基数排序,等。
不稳定的:选择排序。希尔排序,组合排序,堆排序,快速排序,等。
3. 时间复杂度 #
排序算法 | 最优情况 | 最坏情况 | 平均情况 |
---|---|---|---|
冒泡排序 | O(n2) | O(n2) | O(n2) |
插入排序 | O(n2) | O(n2) | O(n2) |
选择排序 | O(n2) | O(n2) | O(n2) |
快速排序 | O(nlogn) | O(n2) | O(nlogn) |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) |
基数排序 | O(n) | O(n) | O(n) |
希尔排序 | 0 | 0 | O(n1.25) |
4. 总结 #
为什么会出现这么多的排序算法,因为没有一个算法能在任何情况下都是最优的,两个算法之间的比对总是在一定的数据量级下进行的。还有就是人们希望能够找到一种更快的排序方式。有些人做过测试,在数据量越大的情况下,快排的优势就越明显。