计数排序(Counting sort)

gaunthan Posted on Aug 7 2016

? Sorting ? ? Algorithm ?

## 概述

**计数排序**(Counting Sort，也称鸽巢排序，Pigeonhole sort)假设n个输入元素中的每一个都是在$[0, k]$ 区间内的一个整数，其中k为某个整数。它需要$O(k)$的存储空间。在实际工作中，当k = O(n)时，一般会采用计数排序，这时排序算法的运行时间为Θ(n)。

计数排序是稳定的，具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序相同。通常，这种稳定性只有当进行排序的数据还附带**卫星数据**(satellite information)时才比较重要。计数排序的稳定性很重要的另一个原因是：计数排序经常会被用作[基数排序算法](http://leanote.com/blog/post/5783b5d2ab644135ea008909)的一个子过程。

## 思想
如果对每一个输入元素 x ，可以确定小于 x 的元素个数。利用这一信息，就可以直接把 x 放到它在输出数组中的位置上。例如，如果有17个元素小于 x，则 x 就应该在第18个输出位置上。当有几个元素相同时，这一方案要略作修改，因为不能把它们放在同一个输出位置上。

## 实现
假设输入是一个序列$A[1...n]，A.length = n$。需要两个数组：$B[1...n]$存放排序的输出，$C[0...k]$提供计数值存储空间。

### 伪代码描述
```c
// A为输入数组；B为输出数组、存放已经排序的数据；k为输入数据的最大值
CountSort(A, B, k)
    let C[0...k] be a new array
    // clear count
    for i = 0 to k
        c[i] = 0
    // count number of each element
    for j = 0 to A.length-1
        C[A[j]] ++
    // C[i] now contains the number of elements equal to i.
    for i = 1 to k
        C[i] += C[i - 1]
    // C[i] now contains the number of elements less than or equal to i.
    for j = A.length-1 downto 0
        value = A[j]
        B[C[value]] = value
        C[value]--
```

### C描述
为求简洁，省略了错误处理代码：
```c
/**
 *@description 计数排序
 *@param int a[]，待排序数组
 *@param int b[]，存放排序的输出
 *@param int n，数组a的元素个数
 *@param int k，数组a的最大元素的值
 *@return 无
 *@notes 代码中的 i 和 j 有不同的代表意义。i代表a[j]，即输入元素的值
*/
void CountSort(int a[], int b[], int n, int k)
{
    int i;
    int *c = (int *)malloc(sizeof(int) * (k + 1));

for(i = 0; i <= k; ++i) // 计数清零
        c[i] = 0;                         
    for(i = 0; i < n; ++i)  // 按值计数加1
        c[a[i]]++;                
    for(i = 1; i <= k; ++i) // 算出小于或等于i的元素个数
        c[i] += c[i - 1];                
    for(i = n - 1; i >= 0; --i) { // 注意这里是反序遍历的，这使得值相同的元素的相对次序不改变
        const int value = a[i];
        b[c[value] - 1] = value; // 在输出数组相应位上放置结果。b[c[a[i]] - 1]，减1是为了让数组的序号从0开始
        --c[a[i]]; // 每放置好一个元素，计数都需要减1
    }
    free(c);    // 释放开辟的堆空间
}
```

## References

- MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010.
- ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013.