【七类排序】之第七种：计数排序

注：若无特殊说明， 排序目的为递增。

最后一篇介绍个线性排序算法，计数排序。 counting sort（计数排序）, radix sort（基数排序）和bucket sort（桶排序）都是可以做到线性时间的。 但是他们都有一些缺陷， 或者理解成特定限制。


首先引用一个结论， 任何comparison sort算法的复杂度下限是nlgn， 简单证明如下：

元素为n的序列一共有n!种排列， 令至少s个比较能够比较出所有元素的先后顺序，假设比较结果不是大于就是小于等于， 因此2^s>=n!
解得s>=log（n!) base 2, 因为 lg (n!) = Ω（nlgn）并且lg(n!) = big O(nlgn), 所以s=Θ（nlgn)。
证毕

回到正题：

counting sort的思想概括成一句话是根据元素出现的频率分配位置， 这不属于comparison sort的范畴，算法描述如下：

输入条件： 长度为n的整形数组a[0..n-1]， for any a, 0<=a<=k, 期中h,k也为整形。
输出： 排序好的数组b[0..n-1]

算法步骤：
1： 统计出每个元素值出现的频率
      initialized array count[]={0}
      For every a[ i ].  count[a[ i ]]++;

2:  根据上一步统计的频率， 计算出每个值的元素应该出现的位置
      For i = 1 to k
           count[ i ] = count[ i-1 ] + count[ i ];

      想一想， 为什么这里是要把前面的值和当前值出现的频率累加？ 假设值为m的元素出现了K次， 那么它排序的位置的位置一定是值为0..m-1的所有元素出现次数总和开始，并且从这之后开始出现count[m]次。


3： 根据步骤2的结果分配位置
      For i = 1 to n {
           place = count [ a[ i ] ];
           b[place] = a;
           count[ a[ i ] ] --; //排入一个， 位置索引减去1。
      }


综上， 时间和空间复杂度为O（max(n,k)）， 如果还有一些附加条件， 比如元素互不重复， 那么可以用Bitmap， 比如用1 Byte = 8 bits标记元素出现的位置， 可以节省更多的空间。计数排序原理非常简单， 但是其中的思想， 即count[ ] 的设计是非常有启发意义的， 很多算法的优化都离不开一些类似的手段，这里不做赘述。

总结：如果有人问过我最喜欢什么算法， 我不会回答dynamic programming, network flow and KMP， 而会说快排， 插入排序这些很基本的算法。排序算法有很多很多， 仅仅我听过的就有15种以上。 他们虽然最终目的是一样的， 但是涉及到了各种各样的原理，截然不同的思想和数据结构。 虽然我认为真正需要掌握的也就那么5,6种而已，但是思考这些简单的算法， 往往能够管中窥豹， 理解那些更多更复杂的东西， 比如nlogn级别中常出现的分治， 比如heap sort中出现的数据结构， 比如merge sort中出现的队列控制， 它们都能引申出更复杂，更有趣的问题。笔者正在研究如何生成decision tree with minimum height，也就是每个节点的分界条件怎么设计才能使得对于与待排序数组用最少的comparison得出结果， 这个问题非常有意思 也是由comparison sort和binary tree的思想引出的。


最后，笔者抛砖引玉写了7篇，鼓励各位把自己对一些算法的理解用自己的语言写成帖子发表，不用顾忌书本教材的行文和条条框框， 要写上你的启发， 你的联想，你的经验。 我想这样是一种最好的学习和讨论方式。

恩，支持，我也争取多写一些。