1. 简介

先举个例子

  • 假设现在有个数组

    1. [1,1,2,6,0,4]

    如果我们不关心这个数组中的顺序, 除了上面的表达方式, 我们还可以用什么办法表示它呢?

  • 我们可以列一个表格 | 数量\元素 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | —- | —- | —- | —- | —- | —- | —- | —- | | \ | 1个 | 2个 | 1个 | 0个 | 1个 | 0个 | 1个 |

  • 这个表格充分表达了数组中有哪些元素

    这个表格能简化吗?

我们可以用一个数组来描述上面这个表格

  1. [1,2,1,0,1,0,1]
  3. //数组的下标表示表格的第一行, 数组中的数字表示表格的第二行
  4. //[1个,2个,1个,0个,1个,0个,1个]
  • 是不是有感觉了?

2. 实现

实现思路

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

Java实现

  1. public static int[] sort(int[] arr)   {
  2.     int maxValue = getMaxValue(arr);//找到数组中元素的最大值
  3.     return countingSort(arr, maxValue);
  4. }
  6. private static int[] countingSort(int[] arr, int maxValue) {
  7.     int bucketLen = maxValue + 1;
  8.     int[] bucket = new int[bucketLen];//根据最大值创建数组
  10.     for (int value : arr) {
  11.         bucket[value]++;
  12.     }
  14.     int sortedIndex = 0;
  15.     for (int j = 0; j < bucketLen; j++) {
  16.         while (bucket[j] > 0) {
  17.             arr[sortedIndex++] = j;
  18.             bucket[j]--;
  19.         }
  20.     }
  21.     return arr;
  22. }
  24. private static int getMaxValue(int[] arr) {
  25.     int maxValue = arr[0];
  26.     for (int value : arr) {
  27.         if (maxValue < value) {
  28.             maxValue = value;
  29.         }
  30.     }
  31.     return maxValue;
  32. }

3. 分析

假设:

  • 元素个数为n

  • 数字最大值为k

    时间复杂度

  • 时间复杂度 = O(n+k)

空间复杂度

  • 时间复杂度 = O(k)

总结

计数排序不是比较排序，排序的速度快于任何比较排序算法。
但由于其与数字最大值k相关, 所以当K很大的时候计数排序就不太适用, 会极大的浪费内存和时间, 例如对时间戳排序