排序算法总结

Author Avatar
Brian Lee 8月 16, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:排序算法总结


比较

算法 是否稳定 是否为原地排序 最好时间 平均时间 最坏时间 辅助空间
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$
插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
希尔排序 $O(n^{1.3})$ $O(1)$
归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$
快速排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ $O(logn)$
堆排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$

稳定 : 如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。

原地排序 :原地排序就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。


一些结论

快速排序时最快的通用排序算法,因为它内循环中的指令很少,而且可以利用缓存。在使用三向切分之后,快速排序对于实际应用中的可能出现的某些分布的输入变成线性级别。

如果稳定性很重要而空间又不是问题,归并排序可能是最好的。

当n较小时,如(n<50),可采用直接插入或简单选择排序,前者是稳定排序,但后者通常记录移动次数少于前者

当n较大时,应采用时间复杂度为 $O(nlgn)$ 的排序方法(主要为快速排序和堆排序)

当n较大时,为避免顺序存储时大量移动记录的时间开销,可考虑用链表作为存储结构(如插入排序、归并排序、基数排序)


源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S2_Sorting


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/08/16/sortSummery/