Java教程

算法基础(七)– 排序算法总结

本文主要是介绍算法基础(七)– 排序算法总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

常见排序算法总结

    • 排序算法汇总
    • 排序算法对比
    • 小结

排序算法汇总

最近对排序算法进行了一些复习,单独对常见的几种排序算法进行了整理总结,汇总如下:

  • 算法基础(三)– 归并排序及其应用
  • 算法基础(四)– 快速排序要点整理
  • 算法基础(五)– 堆结构与堆排序
  • 算法基础(六)– 桶排序:计数排序与基数排序

这里再列上很早之前写的几篇排序相关文章,算是进行一个汇总:

  1. 插入排序–直接插入排序与希尔排序
  2. 交换排序–冒泡排序与快速排序
  3. 选择排序–直接选择与堆排序
  4. 拜托,面试不要问我比较排序了——一文搞懂比较排序
  5. 排序算法——归并排序
  6. 非比较排序之计数排序/桶排序
  7. 分配排序之基数排序

到这里,算是对常见的每一个排序算法有了比较充分的认识,但还缺少一些对他们之间的横向对比。

排序算法对比

算法之间的对比常见的有时间复杂度、额外空间复杂度,对于排序算法来说,还有一个稳定性指标:指同样大小的样本再排序之后不会改变相对次序,如果没有改变,我们称排序算法具有稳定性。

对于基础类型的排序,比如整型,稳定性是没有意义的;而对于非基础类型,稳定性有重要意义。

常见排序算法之间的对比总结如下表:

算法时间复杂度额外空间复杂度稳定性
选择O(N^2)O(1)
冒泡O(N^2)O(1)
插入O(N^2)O(1)
归并O(N*logN)O(N)
快排O(N*logN)O(logN)
堆排序O(N*logN)O(1)
计数O(N)O(M)
基数O(N)O(N)

我们知道,计数、基数排序是非比较的排序方式,对样本数据有严格的规定。
基于比较的排序中,选择、冒泡、插入排序的时间复杂度都相对较高,因此平常不常用。而归并、快排、堆排序都有其各自的特点,适用于不同场景,基于此表格的具体总结如下:

  1. 不基于比较的排序对样本数据有严格的要求,不易于改写;
  2. 基于比较的排序,规定好两个样本如何比较大小,可直接复用;
  3. 基于比较的排序,时间复杂度的极限是O(N*logN);
  4. 时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序不存在;
  5. 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并。

小结

到这里,算是对排序算法做了一个简短的总结,后面继续我的算法旅程,我会继续分享更多算法学习过程中的记录、总结,感谢大家的持续关注。

欢迎关注我的公众号【CoolWrite】,了解更多内容:
我的公众号

这篇关于算法基础(七)– 排序算法总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!