计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为O(n+k)，其中k是整数的范围。基于比较的排序算法时间复杂度最小是O(nlogn)的。该算法于1954年由 Harold H. Seward 提出。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序的特征

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

算法的步骤：

找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

  public void sort(int[] array) {
    int max = array[0], min = array[0];
    for (int a : array) {
      if (a > max) {
        max = a;
      }
      if (a < min) {
        min = a;
      }
    }
    // 申请一个计数数组
    int k = max - min + 1;
    int c[] = new int[k];
    for (int a : array) {
      c[a - min]++;
    }
    //然后为了保持排序稳定，我们需要做一次累加操作
    //这样做的目的，是为了标记出原始数组里面的该元素，前面有几个元素，这个值实际上就是其在原生数组里面的位置，如果有重复的元素，则会先会放置最右边的元素，这样就能保证，排序的稳定性
    for(int i = 1; i < c.length; ++i){
      c[i] = c[i] + c[i-1];
    }
    int len = array.length;
    int[] b = new int[len];
    for (int i = len - 1; i >= 0; --i) {
      //按存取的方式取出c的元素，每取出一个，减一
      b[--c[array[i] - min]] = array[i];
    }
    for (int i = 0; i < len; i ++) {
      array[i] = b[i];
    }
  }

参考资料

https://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F

计数排序

最后更新：2019-12-19

参考资料