插入_选择_交换_归并排序算法总结:扬长避短

2022-07-1717:23:52数据结构与算法Comments1,138 views字数 991阅读模式

1. 排序汇总文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

类别排序方法时间复杂度空间复杂度稳定性
平均情况最好情况最坏情况
插入排序直接插入O(n^2)O(n)O(n^2)O(1)稳定
希尔排序O(n^2)O(n)O(n^2)O(1)不稳定
选择排序直接选择O(n^2)O(n^2)O(n^2)O(1)不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
交换排序冒泡排序O(n^2)O(n)O(n^2)O(1)稳定
快速排序O(nlogn)O(nlogn)O(n^2)O(nlogn)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(1)稳定

2.各个排序面对数据的适用情况与小技巧文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

选取几个比较有特点有代表性质的排序算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

快速排序算法的效率体现在序列越乱的时候,效率越高,当数据趋于一个有序状态时(无论是顺序还是逆序),将会退化为冒泡排序,当数据完全处于逆序状态时,快速排序将会消耗极大的时间,因此有些OJ的快速排序模板测试题并不能直接写快排通过【毒瘤数据,超大完全逆序数据】,可以尝试适用rand()产生随机数的方法将整体数据打乱再使用快速排序,可以极大的减少运行时间。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

直接插入排序有着稳定和速度快的优点,缺点是比较次数越少,插入点后的数据移动就越多,特别是数据庞大的时候就需要大量的移动数据。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

堆排序作为一个相对比较复杂的排序,我们可以更加深入的去借鉴思想,比如有问题要求在n个数据中选出或者排序出前k个数据,利用堆排序的思维可以不将全部的n进行排序而只操作出前k个数据的情况,这个思维是很重要的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

希尔排序最主要的操作是比较而不是交换,因此在小数组的情况下是比快速排序和堆排序要快的,但是涉及大量数据时依旧不如快排。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

对于绝大多数排序在数据达到顺序的情况下并没有办法直接结束,在前置处理数据不是很大的情况下,可以设置一个flag标记,当数据完全处于顺序的情况下直接强制退出排序,以达到减少运行时间的效果,当然前置处理数据在总执行步骤中占比不易过大,如总执行100次,在执行95次的时候已经达到顺序,有5次循环浪费,这样的情况浪费时间不如你而外增添的标记判断时间,就不需要这个flag标记。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

3. 发散性思维文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

上面我们对比切了解到了各种排序的应用情况及优缺点,任何一种排序都不是十全十美的,因此我们最好的方式就是扬长避短,那么请你设计一个算法,能够主动的通过一次遍历去发现数据的情况,究竟最适合何种排序为妙呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25229.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25229.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定