线性排序

之前介绍的最快的排序算法时间复杂度都是O(nlogn)，下面介绍三种时间复杂度为O(n)的排序算法，即：

• 桶排序
  计数排序
  基数排序

这三个排序算法的时间复杂度都是线性的，所以把这类排序算法叫做线性排序

这三种算法的共同点都是：对需要排序的数据有很强的苛刻。

桶排序

将要排序的数据分到几个有序的桶里，每个桶里的数据在单独进行排序。桶内排完之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的。
桶排序比较适合用于外部排序中（也就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存里）。

一个实例
比如说我们有10GB的订单数据，我们希望按照订单金额进行排序，但是我们的内存有限，只有几百MB，没办法一次性把10GB的数据都加载到内存中，这个时候在怎么办呢？
其实我们可以用桶排序来解决这个问题，具体方案是：我们可以先扫描一遍文件，看订单金额所处的数据范围，比如最小是1元，最大是10万元。那么我们可以将所有订单划分到100个桶里，第一个桶存储1值1000之内的订单，每个桶一个文件，以此类推。这样每个文件中存储大约100MB的订单数据，我们可以将这100MB的数据加载到内存中，用快排来排序。等所有文件都排序好之后，你只需要按照上面桶的大小顺序一次读取每个桶里的数据并放到一个文件中，得到的数据就是大排序的订单数据了。但是如果订单金额集中在某个区间，会导致有的桶里数据量非常大，应对的策略是缩小金额较大的区间。比如从1000-2000，缩短到1000-1100。

计数排序

计数排序其实是桶排序的一种特殊情况，当要排序的n个数据范围跨度不大时，比如最大值是k，我们就可以把数据分成k个桶，每个桶内的数值都是相同的。典型的应用场景就是给500万个考生的成绩排序。假设满分是700分的话，我们可以构造701个桶来存放这些考生的数据。

计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，那就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转换为非负整数。

基数排序

我们再来看这样一个排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？

仔细分析这个问题很快就会发现，两个手机号码A、B的大小，如果在前几位中，a手机号码已经比b手机号码大了，那后面几位就不用比了。

基数排序对要排序的数据是有要求的，需要可以分割出独立的位来比较，而且位之间有递进关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。

排序优化

实现通用的排序算法一般都遵循以下原则

不用线性排序算法。虽然时间复杂度第，但是对需要排序的数据有很高的要求；

对小规模数据排序，可以选择时间复杂度是O(n^2)的算法；因为当n比较小时，n^2 < nlogn；

对大规模数据排序时，时间复杂度是O(nlogn)的算法更高效。

谨慎空间复杂度高的排序算法，比如归并排序，虽然时间复杂度低，但是空间复杂度是O(n)，也就是说，对100MB的数据排序，需要消耗200MB的内存。

各大编程语言中的排序算法

比如，Glibc中的qsort()函数，看名字好像是基于快速排序来实现的，但是并不仅仅用了快排这一种思想。去看源码你就会发现，qsort()函数会优先使用归并排序来排序数据，如果数据量大，就会用快排的方式来实现排序。

而Java中的Arrays.sort()函数，则是元素个数小于32，用二分查找插入排序；元素个数>=32，采用归并排序。