计数排序(Counting Sort)是一种非基于比较的排序方法，它要求所有的待排元素都必须是≥0的整数。它的排序步骤是首先根据数组中最大的元素值加1作为长度来定义一个计数数组C。然后统计待排数组中每个值为i的元素出现的次数，存入C的第i项中。再对所有的计数累加（从C中的第一项开始，每一项和前一项相加）。最后再反向填充辅助数组：将每个元素i放在辅助数组的第C(i)项，每放一个元素就将C(i)减去1。这样完成之后排序就已完毕，有序序列已存储在辅助数组中。如果结果想用原数组输出，则将它们从辅助数组考回到原数组即可。

计数排序的C/C++代码实现：

void counting_sort(int a[], int length)
{
    int i;
    int c[MAX_VALUE] = {0};
    int tmp[ARRAY_SIZE] = {0};
    for (i = 0; i < length; ++i) c[a[i]]++;
    for (i = 1; i < MAX_VALUE; ++i) c[i] += c[i-1];
    for (i = length - 1; i >= 0; --i) {
        tmp[ c[a[i]]-1] = a[i];
        c[a[i]]--;
    }
    for (i = 0; i < length; ++i) a[i] = tmp[i];
}

计数排序是稳定的排序方法，这是它很重要的特性之一，也是为什么要在这里介绍它的原因：因为后面的LSD基数排序会因为它的这个特性而用到它。

计数排序的时间复杂度是O(n)，比之前所讲的所有比较排序算法都快。但由于它的限制条件苛刻，比如所排元素必须是≥0的正整数，并且数据范围和数据元素个数不宜过大等。虽然经过改进可以对数据项较大、包含范围较小的文件进行排序，但应用范围仍然不是很大。