原理

  • 使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数，然后根据数组C来确定A中数组排到正确的地方

  • 步骤

    • 计算每个数出现了几次
    • 求出每个数出现次数的前缀和
    • 利用出现次数的前缀和，从右至左计算出每个数的排名

      性质

  • 稳定性：稳定的

  • 时间复杂度：计数排序 - 图1，其中w是待排序数据的值域大小

    代码

    1. public void counting_sort(int[] a) {
    2.   final int MAX = 10000;
    3.   int[] count = new int[MAX + 1];
    4.   int[] b = new int[a.length];
    5.   for (int i = 0; i < a.length; i++) {
    6.       count[a[i]]++;
    7.   }
    8.   for (int i = 1; i < count.length; i++) {
    9.       count[i] += count[i - 1];
    10.   }
    11.   for (int i = a.length - 1; i >= 0; i--) {
    12.       b[--count[a[i]]] = a[i];
    13.   }
    14.   for (int i = 0; i < a.length; i++) {
    15.       a[i] = b[i];
    16.   }
    17. }