一种特殊的排序算法 II

一种特殊的排序算法 II

  -- 计数排序(Counting sort)

---

后续想找时间再写一篇《一种特殊的排序算法 II》，关于计数排序☺。（引自 《一种特殊的排序算法 I》）

所以，继上篇文章《一种特殊的排序算法 I》，在此就（继续）描述，总结另一种特殊的排序算法，计数排序。算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素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。

(完）