从第一篇《算法概要》开始,到此篇已经经历了将近四个月时间,常见的基础排序已经温习完成
内部排序:待排序记录存放在计算机随机存储器中(说简单点,就是内存)进行的排序过程
外部排序:待排序记录的数量很大,以致于内存不能一次容纳全部记录,所以在排序过程中需要对外存进行访问的排序过程
内部排序:比较次数,也就是时间复杂度
外部排序:IO次数,也就是读写外存的次数
IO对排序的影响可以阅读《深入浅出索引》体会
冒泡排序,应该是很多人会且只会的算法;两两比较交换
为了减小比较与交换的次数,通过双向比较(鸡尾酒排序)、设定是否交换位实现
快速排序,相对冒泡又改进了,都是交换,但引入了分治思想
插入排序,像打牌时,整理牌一样,通过比较、移动来达到排序
希尔,相对插入做了改进,不是一步一步的移动,而是大步大步的移动
选择,类似插入的反向操作;插入排序是边读边排,每当读入一个新的数时,目前的数组一定是排好序的。而选择排序不同,它必须是读完所有的数据之后才能开始排序的
堆排序,借助堆数据结构,构造堆结构,选取堆顶元素,不再需要遍历所有元素选择
归并排序,也是分治思想,但与快速有些区别;归并排序是由下向上的,先处理子数组然后再合并。而快速排序正好相反,它的过程是由上向下的,先分出两个子区间,再对子区间进行排序
线性排序算法,非基于比较的排序算法,性能很高,但都有限制才能达到线性排序的效果
对于排序算法选择,不能单从时间复杂上看,简单算法都是O(n^2),就不考虑,只选择改进算法
由下图可以看出,在输入规模小于100时,插入排序要好于归并和快速排序。在输入规模小于200时,插入排序优于归并排序。规模在30以下时,插入排序效率要比快速排序高50%以上,规模在50以下时,插入排序比归并排序效率高90%以上
在数据量大时,使用改进算法
总的来说,并不存在“最佳”的排序算法。必须针对待排序列自身的特点来选择“良好”的算法。下面有一些指导性的意见:
【京东】假设你只有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),所以这里我们应该选择堆排序
基于比较的内部排序总结
常见比较排序算法的耗时测试