线性排序

如何根据年龄给100万数据排序？

时间复杂度O(n)的排序算法：桶排序、计数排序、基数排序。

桶排序

将要排序的数据分到几个有序的桶里。每个桶里的数据可单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。时间复杂度是O(n)

桶排序对数据要求非常苛刻。

1. 要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。这样桶内排完序之后，桶外就不需要排了。
2. 数据在各个桶之间分布是比较均匀的，如果桶里的数据分布不均，排序就会很复杂。

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

计数排序

计数排序其实是桶排序的一种特殊情况。
当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。
比较高考成绩，将每一个成绩列为一个桶，满分900，划分为901个桶，桶内的成绩不需要排序。整体只需要遍历一遍，将成绩划分到桶内就行。

A是原始数组，C存储的是小于等于分数k的个数，R排序之后的有序数组。

// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
  if (n <= 1) return;
  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }
  int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }
  // 计算每个元素的个数，放入c中
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }
  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }
  // 临时数组r，存储排序之后的结果
  int[] r = new int[n];
  // 计算排序的关键步骤，有点难理解
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }
  // 将结果拷贝给a数组
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

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

基数排序

假设给10万个手机号码排序。
先排第一位，第一位排完再排第二位，稳定排序。
手机号是等长的，也有不等长的字母，可以用补零的方式。

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

小结

今天学习的这三种排序方式，有相似性，也有局限性，都对数据要求比较严格。桶排序和计数排序比较相似，针对范围不大的数据，将数据划分成不同的桶来实现。基数排序要求数据有高低位之分，位之间有递进关系，只需要先比较高位，高位相同在比较低位，每一位数据范围不能太大。