一种特殊的排序算法 II
-- 计数排序(Counting sort)
后续想找时间再写一篇《一种特殊的排序算法 II》，关于计数排序☺。（引自 《一种特殊的排序算法 I》）
所以，继上篇文章《一种特殊的排序算法 I》，在此就（继续）描述，总结另一种特殊的排序算法，计数排序。算法的步骤如下：
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
引用自维基内容，完整介绍可以参见计数排序（维基）。
（后面，开始分享我的内容）
关于计数排序（算法），可以划分两种具体的计数法，如下：
* 比较计数法
* 分布计数法
===
> 比较计数法
算法 ComparisonCountingSort(A[0 ... n-1])
// 用比较计数法对数组排序
// 输入:可排序数组 A[0 ... n-1]
// 输出:将A中元素按照升序排列的数组 S[0 ... n-1]
for i : 0 to n-1 do
Count[i] = 0;
for i : 0 to n-2 do
for j : i+1 to n-1 do
if A[i] < A[j]
Count[j] += 1;
else
Count[i] += 1;
for i : 0 to n-1 do
S[Count[i]] = A[i];
return S;
该算法的时间效率如何？答案为O(n^2)。因为该书法执行的键值比较次数和选择排序一样多，并且还占用了线性数量的额外空间，我们几乎不能推荐它来实际的应用。但是计数思想在一种情况下还是卓有成效的，在这种情况下，待排序的元素的值都来自于一个已知的小集合，这就是下面要描述的另一种计数排序算法，分布计算法。
===
> 分布计数法
算法 DistributionCountingSort(A[0 ... n-1, l, u])
// 用分布计数法对数组排序,对来自于有限范围整数的一个数组进行排序
// 输入:可排序数组 A[0 ... n-1],数组中的整数位于l和u之间( l <= u)
// 输出:将A中元素按照升序排列的数组 S[0 ... n-1]
for i : 0 to u-l do
D[i] = 0; // 初始化频率数组
for i : 0 to n-1 do
D[A[i] - l] = D[A[i] - l] + 1; // 计算频率值
for i : 1 to u-l do
D[i] = D[i-1] + D[i]; // 重用于分布值
for i : n-1 downto 0 do
j = A[i] - l;
S[D[j] - 1] = A[i]; // D[j] - 1]为对应的数组下标
D[j] -= 1;
return S;
注：频率值，表示元素出现的次数；分布值表示在最后有序数组中，元素最后一次出现的位置。
假设数组值的范围是固定的，这显然是一个线性效率的算法，因为它仅仅对输入数组A从头到尾连续处理两遍，其时间复杂度 O(n)。然而，要重点记忆的是，除了空间换时间之外，分布计数排序这种高效率是因为利用了输入列表独特的自然属性。
===
附：
文章内容乃学习心得（笔记），亦包括引用自《算法设计与分析基础（第2版）》内容（第七章时空权衡，7.1计数排序）。
以上描述的算法，以C\C++完成了简单的实现，示例代码参见 github。
