计数排序是一种排序算法，它通过计算数组中每个唯一元素的出现次数来对数组的元素进行排序。计数存储在辅助数组中，排序是通过将计数映射为辅助数组的索引来完成的。

算法的图解

从给定数组中找出最大元素（让它成为 max）。 | | | —- | | 给定数组 |

初始化一个长度为 max+1，且所有元素为 0 的数组。该数组用于存储数组中元素的计数。 | | | —- | | 计数数组 |

将每个元素的计数存储在计数数组中各自的索引处

存储计数数组元素的累积总和。它有助于将元素放入已排序数组的正确索引中。


累计次数

在 count 数组中找到原始数组的每个元素的索引。这给出了累积计数。将元素放置在计算出的索引处，如下图所示。


计数排序

将每个元素放在正确的位置后，将其计数减一。

算法的伪码

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

算法的实现

// Counting sort in Java programming
import java.util.Arrays;
class CountingSort {
  void countSort(int array[], int size) {
    int[] output = new int[size + 1];
    // Find the largest element of the array
    int max = array[0];
    for (int i = 1; i < size; i++) {
      if (array[i] > max)
        max = array[i];
    }
    int[] count = new int[max + 1];
    // Initialize count array with all zeros.
    for (int i = 0; i < max; ++i) {
      count[i] = 0;
    }
    // Store the count of each element
    for (int i = 0; i < size; i++) {
      count[array[i]]++;
    }
    // Store the cummulative count of each array
    for (int i = 1; i <= max; i++) {
      count[i] += count[i - 1];
    }
    // Find the index of each element of the original array in count array, and
    // place the elements in output array
    for (int i = size - 1; i >= 0; i--) {
      output[count[array[i]] - 1] = array[i];
      count[array[i]]--;
    }
    // Copy the sorted elements into original array
    for (int i = 0; i < size; i++) {
      array[i] = output[i];
    }
  }
  // Driver code
  public static void main(String args[]) {
    int[] data = { 4, 2, 2, 8, 3, 3, 1 };
    int size = data.length;
    CountingSort cs = new CountingSort();
    cs.countSort(data, size);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

算法复杂性

时间复杂度
最好的	O(n+k)
最差	O(n+k)
平均	O(n+k)
空间复杂度	O(max)
稳定	是的

时间复杂度

主要有四个主要循环。（可以在函数外找到最大值。）

for循环	计数时间
1st	O(max)
2nd	O(size)
3rd	O(max)
4th	O(size)

整体复杂度 = O(max)+O(size)+O(max)+O(size) = O(max+size)

最坏时间复杂度： O(n+k)
最佳时间复杂度： O(n+k)
平均时间复杂度： O(n+k)

在上述所有情况下，复杂度是相同的，因为无论元素如何放置在数组中，算法都会经历 n+k 次。任何元素之间都没有比较，因此它比基于比较的排序技术更好。但是，如果整数非常大，那就不好了，因为应该制作该大小的数组。

空间复杂度

计数排序的空间复杂度为O(max). 元素范围越大，空间复杂度就越大。

算法的应用

在以下情况下使用计数排序：

有多个计数的较小整数
线性复杂度是需要的

相似的算法

快速排序
归并排序
桶排序
基数排序

数据结构与算法

计数排序（Counting Sort）