Wenzi

排序算法之总结

蚊子前端博客
发布于 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)
希尔排序 0 0 O(n1.25)

4. 总结 #

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

标签:sort
阅读(470)
Simple Empty
No data