线性排序

时间复杂度为线性（ O(n) ）的排序方式叫做线性排序。常见的线性排序有桶排序、计数排序、基数排序。

桶排序

（1）就是将数据放入已经排好序的桶中，然后对桶中的数据分别进行排序，最后按照桶的顺序将数据拿出来，就是排完序的样子。
例如：需要对100万个用户按照年龄进行排序，可以将0-9岁的放到1号桶，10-19岁的放到2号桶，20-29岁的放到3号桶。。。。100-119岁。。。然后在将各个桶里面的数据利用其它排序方法（例如快排）排好序，最后按照桶的大小顺序将元素取出来。
（2）

    private int indexFor(int a, int min, int step) {
        return (a - min) / step;
    }

    public void bucketSort(int[] arr) {

        int max = arr[0], min = arr[0];
        for (int a : arr) {
            if (max < a)
                max = a;
            if (min > a)
                min = a;
        }
        // 桶的个数
        int bucketNum = max / 10 - min / 10 + 1;
        List buckList = new ArrayList<List<Integer>>();
        // 创建桶
        for (int i = 1; i <= bucketNum; i++) {
            buckList.add(new ArrayList<Integer>());
        }
        // 将数据放入合适的桶中
        for (int i = 0; i < arr.length; i++) {
            int index = indexFor(arr[i], min, 10);
            ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
        }
          // 将排好序的数放入原数组中
        ArrayList<Integer> bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList<Integer>) buckList.get(i);
            insertSort(bucket);
            for (int k : bucket) {
                arr[index++] = k;
            }
        }

    }

    // 把桶內元素插入排序
    private void insertSort(List<Integer> bucket) {
        for (int i = 1; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

（3）时间复杂度分析：
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

（4）桶排序的弊端：
要保证桶排序法的时间复杂度为线性的，需要让各个桶内的元素数量均匀，如果出现极端情况，比如所有的元素都几种到了同一个桶里面，那么桶排序的时间复杂度就会退化为O(nlogn)。由此看来，桶排序的应用场景非常有限。

计数排序

（1）计数排序法是一种特殊的桶排序法，它是将数据范围缩到最小。
例如：同样是将100万个人按照年龄排序，可以将0岁放入1号桶，2岁放入2号桶。。。。。

（2）那么“计数”体现在什么地方？
同样是上面的例子，我们将数据规模缩小来说明这个事。
假如有8位小朋友，年龄分别是：2，5，3，0，2，3，0，3
创建一个数据来存储各个年龄的人数：

数组：[2,0,2,3,0,1]
索引：[0,1,2,3,4,5]

事实上现在除了知道每个年龄的人数之外，还知道了在它前面有多少人。比如：3岁的有3人，前面有4人。

（3）应用中，为了把这个事办的更省心一些，会直接在每一个年龄的上面标一个数字，这个数字表示该年龄前面所有年龄人数之和加上该年龄的人数。例如：上面的例子

个数：[2,2,4,7,7,8]
年龄：[0,1,2,3,4,5]

排序的时候，遍历到第一个3的时候，将它放到索引为6的位置，然后将它上面的数字减一，第二次遇到3时，将它放到第5的位置，上的数字再减一，所有的年龄都是同样的操作。

（4）

// 计数排序，a 是数组。假设数组中存储的都是非负整数。
public void countingSort(int[] a) {
  if (a.length <= 1) return;

  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i < a.length; ++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 < a.length; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 临时数组 r，存储排序之后的结果
  int[] r = new int[a.length];
  // 计算排序的关键步骤
  for (int i = a.length - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 将结果拷贝给 a 数组
  for (int i = 0; i < a.length; ++i) {
    a[i] = r[i];
  }
}

待续。。