线性排序

时间复杂度为O(n)的线性排序算法：桶排序、计数排序、基数排序。
算法是非基于比较的排序算法（主排序是非比较的），不涉及元素之间的比较操作。对要排序的数据要求比较苛刻。

桶排序

• 原理
  核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

• 时间复杂度
  如果要排序的数据有n个，把他们均匀的划分到m个桶内，每个桶有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(klogk)。m个桶排序的时间复杂度为O(mklogk)。因为k=n/m，所以整个桶排序的时间复杂度为O(nlog(n/m))。当桶的个数m接近数据个数n时，log(n/m)为一个非常小的常量，这时桶排序的时间复杂度接近O(n)。

• 适用场景
  排序的数据需要很容易就能划分为m个桶，桶与桶之间有着天然的大小顺序，每个桶内的数据都排序完成之后，桶与桶之间的数据不需要再进行排序。
  数据再各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有的桶数据非常多，有的非常少，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为O(nlogn)的排序算法了。

  桶排序适合用在外部排序中。数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

计数排序

• 时间复杂度
  计数排序是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值为k，可以把数据划分成k个桶，每个桶内的数据值都是相同的，省去了桶内排序的时间。只涉及扫描遍历操作，时间复杂度为O(n)。

• 原理
  计数排序用一个数据范围大小的统计数组C[k+1]（原数组A中元素取值范围为0-k），下标k等于原数组A中元素的值，遍历原数组A将各个元素值出现的次数存储在统计数组C对应下标中c[k]（即C[k]存储的是原数组A等于k的元素的个数）。然后对统计数组C顺序求和，各个下标处C[k]存储的是小于等于k的元素个数。
  扫描原数组A（从后面开始遍历-保证稳定性），依次取出元素的值如a作为统计数组C的下标得到统计数组C对应的值C[a]，说明到目前为止，原数组A中小于等于a的值还有C[a]个，元素a是排好序的新数组R中的第C[a]个元素(放在新数组R下标为C[a]-1的位置)，将其a放入新数组R后，原数组A小于等于a的元素剩下C[a]-1个，则统计数组C[a]=C[a]-1，类推取原数组A下一个元素值。（从后往前做减法，确定该值可以放的最大下标）

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

基数排序

• 原理
  以11位手机号排序为例，如果前面几位中，其中一个数据已经比较大了，那么后几位就不用看了。先按照最后一位排序，再按照倒数第二位排序，以此类推，最后按照第一位排序，经过11次排序后，手机号有序。要求按照每位来排序的排序算法是稳定的。

• 时间复杂度
  根据每位来排序，可以用桶排序或者计数排序，时间复杂度可以做到O(n)。如果要排序的数据有k位，那么需要进行k次桶排序或者计数排序，总的时间复杂度是O(k*n)。当k不大时，基数排序的时间复杂度就近似于O(n)。

• 适用场景
  基数排序要求要排序的数据可以分割出独立的“位”来比较，而且位之间有递进关系-数据可以划分成高低位。比较两个数只需要比较高位，高位相同再比较低位。
  每一位的数据范围不能太大，要借助线性排序算法-桶排序/计数排序来完成每一位的排序工作，否则计数排序的时间复杂度无法做到O(n)。

总结

桶排序：分桶-快排/归并
计数排序：分桶-计数-统计
基数排序：高位桶排序-低位桶排序