排序算法之总结

蚊子前端博客
发布于 2012-12-04 07:00
原本还打算写希尔排序和堆排序呢,不过由于时间原因也只能写这些排序了。下面总结和对比一下常用的排序方法吧

原本还打算写希尔排序和堆排序呢,不过由于时间原因也只能写这些排序了。下面总结和对比一下常用的排序方法吧。

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)
希尔排序00O(n1.25)

4. 总结

为什么会出现这么多的排序算法,因为没有一个算法能在任何情况下都是最优的,两个算法之间的比对总是在一定的数据量级下进行的。还有就是人们希望能够找到一种更快的排序方式。有些人做过测试,在数据量越大的情况下,快排的优势就越明显。

标签:
阅读(283)

公众号:

qrcode

微信公众号:前端小茶馆

公众号:

qrcode

微信公众号:前端小茶馆