在满足了输入的元素属于一个有限集合的前提下，counting sort 可以在线性时间内完成排序。Counting sort 的算法过程中没有比较过一次元素，它是通过元素的键及出现的频率来决定元素按顺序排列后的位置。这有别于基于比较的排序算法，如归并排序、快速排序、插入排序，在最好的情况下也至少需要线性对数级时间（n*log(n)）完成排序（这个可以通过构建决策树来证明，当 n = 节点数量时，决策树的高度不会小于 n*log(n)）。
Counting sort 的思想是：建立一个元素出现的频率表，通过查找每个元素出现的频率可得知元素最后应排列在什么位置。
先假设元素的键就是元素的值，且属于 { 0, 1, …, k } 这个集合，这是最简单的一种情况。如：对于 [ 1, 0, 4, 0, 3 ] 这个数组，其元素属于的有限集合为 { 0, 1, 2, 3, 4 }，k=4，集合大小为 5，而 freq(0)=2, freq(1)=1, freq(2)=0, freq(3)=1, freq(4)=1。如此便知两个 0 必在最前，1 前面有两个元素（0），2 没有出现，3 前面有两个元素（0）加上一个元素（1），4 前面有有两个元素（0）加上一个元素（1）再加上一个元素（3）。由于假设了元素的键就是元素的值，在频率表构建完成后可以按键的大小顺序遍历整个频率表，依次在输出数组末尾添加频率那么多个的键，最后整个输出数组就是已经排序完成的输入数组了。如果没有作出上述假设，这里添加的就必须是频率那么多个的值。
可以用 C 来实现上述过程。频率表 count 是一个数组，其索引是元素的键，其值是频率，如 count[2] 是 2 出现的频率。这里的 arr 是输入数组，size 是数组大小，而 bound 相当于上述的 k+1，{ 0, …, k } 的大小。
void
counting_sort(int arr[], int size, int bound)
{
int i;
int* count = calloc(bound, sizeof (int));
/* Construct frequency table. */
for (i = 0; i < size; ++i)
++count[arr[i]];
/* Append to output array based on frequency. */
for (i = 0; i < bound; ++i)
while (--count[i] >= 0)
*arr++ = i;
}
这是一个简洁明了的实现，时间复杂度∈Ɵ(size+bound)，空间复杂度∈Ɵ(bound)。由于元素只是简单的整数，也不需要考虑排序算法稳定性的问题，因为两个值相等的整数通常被认为是不可区分的。然而，当元素的键并不是元素的值时，这个实现就不靠谱了——不能直接 *arr++ = i，而需要 *arr++ = value(i)。key(value) 可以由调用者提供，那 value(key) 呢？强行按照以上思路来实现还需要一个键到多个值的映射。稳定性也是个问题。
不妨换一种思路：保存元素的累积频率（即元素本身出现的频率加上所有更小的元素出现的频率之和），通过一个元素的累积频率可得知小于等于该元素的所有元素的频率之和，也就能直接确定元素最终的位置了。比如：元素的累积频率为 10，说明一共有 10 个小于等于该元素的元素（包括該元素本身），那么该元素应该被放在输出数组的第 10 个元素的位置上。用这种方式的话就可以通过遍历元素的值来实现，也就能访问元素的值本身了。
void
counting_sort(void* arr[], int size, int bound, int (*key)(void*))
{
int i;
int* count = calloc(bound, sizeof (int));
void** sorted = malloc(size * sizeof (void*));
/* Construct frequency table. */
for (i = 0; i < size; ++i)
++count[key(arr[i])];
/* Construct cumulative frequency table. */
for (i = 1; i < bound; ++i)
count[i] += count[i - 1];
/* Sort based on key positions. Iterate backwards to be stable. */
for (i = size - 1; i >= 0; --i)
sorted[--count[key(arr[i])]] = arr[i];
memcpy(arr, sorted, size * sizeof (void*));
}
这种实现的时间复杂度同样∈Ɵ(size+bound)，但空间复杂度∈Ɵ(size+bound)，因为需要额外使用 size 大小的数组作为临时存储。
需要注意的有两点：一是最后一个循环是反向迭代，二是每次要递减累积的频率。后者是针对相等元素的特殊处理——累积频率指定的是相等的元素中最后一个元素（离数组开头最远）的位置，那么下一次遇到相等元素时就应该朝数组开头移动一个索引，这样才不会导致所有相等的元素都被放到了同一个位置。另一方面，为了保证稳定性，这个过程必须与反向迭代配合，因为如果正向迭代，相等元素中先出现的反而会被放到离数组开头更远的位置。这个算法可以通过改变累积频率的存储方式来反转：如果一个元素的累积频率变为不包括该元素本身及相等元素的频率而只是小于它的元素的频率之和，那便可以从 0 迭代到 size-1，并且每次递增累积频率。
测试：
int
key(void* value)
{
switch ((uintptr_t) value) {
case 0:
case 1:
case 2:
case 3:
return (int) value;
case 5:
return 4;
case 7:
return 5;
case 9:
return 6;
}
}
int
main()
{
uintptr_t arr[] = { 3, 0, 9, 1, 0, 5, 7, 2, 5 };
int i, size = sizeof (arr) / sizeof (uintptr_t);
counting_sort((void**) arr, size, 7, key);
//{
for (i = 0; i < size; ++i)
printf("%d ", arr[i]);
printf("\n");
//} => 0 0 1 2 3 5 5 7 9
return 0;
}
这里的 key() 纯粹是为了测试目的而定义的完美散列函数，测试代码中出现的 7 个唯一的整数将会被完美地映射到 0..6 这 7 个键。
由于 counting sort 的前提是输入的元素属于一个有限集合，并且在计算过程中将会使用这个集合那么大的额外空间，它并不是一种通用的排序算法。实践时，通用的排序算法通常需要能够处理所有 16、32 甚至是 64 位整数，其值域的大小通常大于物理内存所能容纳的空间。基于 counting sort 之上的radix sort（基数排序）则是一个典型的可通用于更大范围值域的非比较的排序算法。
第七水螰 