前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一篇解决排序算法

一篇解决排序算法

作者头像
码农戏码
发布2021-03-23 10:54:04
5040
发布2021-03-23 10:54:04
举报
文章被收录于专栏:DDD

从第一篇《算法概要》开始,到此篇已经经历了将近四个月时间,常见的基础排序已经温习完成

内外排序

内部排序:待排序记录存放在计算机随机存储器中(说简单点,就是内存)进行的排序过程

外部排序:待排序记录的数量很大,以致于内存不能一次容纳全部记录,所以在排序过程中需要对外存进行访问的排序过程

衡量效率

内部排序:比较次数,也就是时间复杂度

外部排序:IO次数,也就是读写外存的次数

IO对排序的影响可以阅读《深入浅出索引》体会

算法

详细介绍

算法渣-排序-冒泡

冒泡排序,应该是很多人会且只会的算法;两两比较交换

为了减小比较与交换的次数,通过双向比较(鸡尾酒排序)、设定是否交换位实现

算法渣-排序-快速排序

快速排序,相对冒泡又改进了,都是交换,但引入了分治思想


算法渣-排序-插入

插入排序,像打牌时,整理牌一样,通过比较、移动来达到排序

算法渣-排序-希尔

希尔,相对插入做了改进,不是一步一步的移动,而是大步大步的移动


算法渣-排序-选择

选择,类似插入的反向操作;插入排序是边读边排,每当读入一个新的数时,目前的数组一定是排好序的。而选择排序不同,它必须是读完所有的数据之后才能开始排序的

算法渣-排序-堆排序

堆排序,借助堆数据结构,构造堆结构,选取堆顶元素,不再需要遍历所有元素选择


算法渣-排序-归并排序

归并排序,也是分治思想,但与快速有些区别;归并排序是由下向上的,先处理子数组然后再合并。而快速排序正好相反,它的过程是由上向下的,先分出两个子区间,再对子区间进行排序


算法渣-排序-基数排序

算法渣-排序-桶排序

算法渣-排序-计数排序

线性排序算法,非基于比较的排序算法,性能很高,但都有限制才能达到线性排序的效果

场景

对于排序算法选择,不能单从时间复杂上看,简单算法都是O(n^2),就不考虑,只选择改进算法

插入排序 vs 快速排序 vs 归并排序

由下图可以看出,在输入规模小于100时,插入排序要好于归并和快速排序。在输入规模小于200时,插入排序优于归并排序。规模在30以下时,插入排序效率要比快速排序高50%以上,规模在50以下时,插入排序比归并排序效率高90%以上

改进算法

在数据量大时,使用改进算法

  1. 就时间性能而言, 希尔排序、快速排序、树形选择排序、堆排序和归并排序都是较为先进的排序方法。耗时远小于O(N^2)级别的算法。
  2. 先进算法之中,快排的效率是最高的。 但其缺点十分明显:在待排序列基本有序的情况下,会蜕化成起泡排序,时间复杂度接近 O(N^2)。
  3. 希尔排序的性能让人有点意外,这种增量插入排序的高效性完全说明了:在基本有序序列中,直接插入排序绝对能达到令人吃惊的效率。但是希尔排序对增量的选择标准依然没有较为满意的答案,要知道增量的选取直接影响排序的效率。
  4. 归并排序的效率非常不错,在数据规模较大的情况下,它比希尔排序和堆排序都要好。
  5. 堆排序在数据规模较小的情况下还是表现不错的,但是随着规模的增大,时间代价也开始和上面两种排序拉开的距离。

总结

总的来说,并不存在“最佳”的排序算法。必须针对待排序列自身的特点来选择“良好”的算法。下面有一些指导性的意见:

  1. 数据规模很小,而且待排序列基本有序的情况下,选择直接插入排序绝对是上策。不要小看它O(N^2)级别
  2. 数据规模不是很大,完全可以使用内存空间。而且待排序列杂乱无序(越乱越开心),快排永远是不错的选择,当然付出log(N)的额外空间是值得的。
  3. 海量级别的数据,必须按块存放在外存(磁盘)中。此时的归并排序是一个比较优秀的算法

试题

【京东】假设你只有100Mb的内存,需要对1Gb的数据进行排序,最合适的算法是( )

A. 归并排序  B. 插入排序  C. 快速排序  D. 冒泡排序

根据题目,我们可以知道,我们现有的内存限制使得我们无法把数据一次性加载到内存中,所以我们只能先加载一部分数据,对其排序后存入磁盘中。然后再加载一些数据,把它们“合并”到已排序的数据集中去,重复这个过程直到排序完成,显然最能胜任这个工作的是归并排序。

【2016阿里巴巴校招笔试题】现有1GB数据进行排序,计算资源只有1GB内存可用,下列排序方法中最可能出现性能问题的是( )

A. 堆排序  B. 插入排序  C. 归并排序  D. 快速排序  E. 选择排序  F. 冒泡排序

根据题目的描述,我们能够很明确的知道这道题考察我们的是原地排序的概念,这里我们只需要选择非原地排序的占用额外空间最大的算法,显然答案是”C. 归并排序"。

【2015阿里巴巴研发工程师笔试题】个数约为50K的数列需要进行从小到大排序,数列特征是基本逆序(多数数字从大大小,个别乱序),以下哪种排序算法在事先不了解数列特征的情况下性能最优

A. 冒泡排序  B. 改进冒泡排序  C. 选择排序  D. 快速排序  E. 堆排序  F.插入排序

根据题目中的描述,首先我们可以排除A、B、C,因为它们的时间复杂度都是O(n^2)。接下来我们看下D选项,我们前面提到过,快速排序在最坏情况下的时间复杂度会退化至O(n^2),F选项的插入排序在逆序数很大时性能也很差(O(n^2))。而堆排序在最坏情况下的复杂度也为O(logn),所以这里我们应该选择堆排序

参考资料

基于比较的内部排序总结

常见比较排序算法的耗时测试

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码农戏码 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 内外排序
    • 衡量效率
    • 算法
      • 详细介绍
        • 场景
          • 插入排序 vs 快速排序 vs 归并排序
          • 改进算法
          • 总结
      • 试题
      • 参考资料
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档