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

内外排序

内部排序：待排序记录存放在计算机随机存储器中（说简单点，就是内存）进行的排序过程

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

衡量效率

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

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

参考资料

基于比较的内部排序总结

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