算法渣-排序-总结

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

内外排序

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

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

衡量效率

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

外部排序: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),所以这里我们应该选择堆排序

参考资料

基于比较的内部排序总结

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

朱兴生 wechat
最新文章尽在微信公众号『码农戏码』