线性排序

这类排序算法的时间复杂度是线性的，统称 线性排序。

之所以能够做到线性复杂度，原因就是：这些算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序(Bucket Sort)

桶排序 的核心思想是将要排序的数据分到若干个有序的“桶”中，每个桶里的数据再做单独排序。桶排完序之后，再把每个桶的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序的时间复杂度为什么为：O(n)。

数据：n 条
桶：m 个
每个桶数据：n/m 条
每个桶快排时间复杂度：O(k*logk)
m 个桶时间复杂度:O(m*k*logk) = O(m*(n/m)logk) = O(nlogk) = O(nlogn/m)
m ~= n 的时候，O(nlogn/m) ~= O(n)

也就是当桶个数与数据非常接近，log(n/m)是一个非常小的常量，这个时候的排序时间复杂度为 O(n)。

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

要排序的数据要很容易划分成 m 个桶。
桶与桶之间要有着天然的大小排序。这样内部数据排序之后，桶不需要再次排序。
每个桶的数据划分比较均匀，这样桶内部的时间复杂度就会接近一个很小的常数。

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

记数排序

可以理解为是 桶排序 的一种。要排序的数据在一定的范围内，比如最大值为 k。我们把数据划分为 k 个桶，每个桶的数据值是相同的，这样省掉了排序的时间。

举个例子：有8个考生，分数在0～5之间，考生成绩分别为：2，5，3，0，2，3，0，3


// 计数排序，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];
  }
}

记数排序 要求数据范围不大，而且最好是给非负数整数排序，如果数据含有负数，需要做一次运算，将所有的值加上一个常数以此将数据转化为正数。

基数排序（Radix Sort）

以手机号码为例：将数据分为11位，从最后一位开始排序，然后最后第二位，以此类推，最后以第一位进行排序，最终得到有序列表。每一位的排序可以使用线性排序算法进行排序。时间复杂度为 O(11*n) = O(n)

基数排序需要满足一些条件：

数据可以分割出独立的位来排序，位之间有递进的关系。
每一位的数据范围不能太大，可以用线性排序算法排序。

Notes：数据位数不同时，可以使用“0”补齐

November 27, 2018

桶排序(Bucket Sort)

记数排序

基数排序（Radix Sort）