高考分数排序之计数排序
在社会上摸爬滚打了几年，见识了一些人和事，越发意识到高考的重要性。很多高校和企业在招聘时，都非常看重学历(甚至是第一学历)，这种筛选条件很世俗，但从概率的角度来看，合情合理。
高考成绩马上就要出来了，来聊聊与高考相关的算法问题。
问题：参加全国高考数学考试的人数为n, 数学满分为k(k=150), 求数学分数的排序结果。要求：时间复杂度为O(n).
对于排序算法，大家已经耳熟能详了，冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序、归并排序，它们都是基于比较的排序。可以从数学上证明：基于比较的排序的时间复杂度最好能达到O(NlogN).
显然，基于比较的排序，无法满足题目中的时间复杂度要求。那么，有没有时间复杂度为O(n)的排序算法呢？有的！比如计数排序，它依赖于计数，而非比较。
如果直接提出计数排序，就太经验主义了，不利于能力的提高。对于困难问题，要学会分解和简化，然后各个击破。
我们来简化上述问题：假设高考人数n=4, 数学满分k=3, 而且这4个考生的分数都不相同，试对考生分数进行排序。
这个问题就很简单了，考生的分数取值只可能是0,1,2,3, 现在4个考生的分数都不相同，那么他们的分数的排序结果是0,1,2,3.
显然，这是一种很特殊的情况：每个分数值都有且仅有1个人占据。其实，高考分数的实际情况是：某个分数值可能有c个人占据(0<=c<=n), 我们需要处理这种情况，实际上是对分数值上的人数进行计数，然后排序，这就是计数排序。
我们来看看计数排序的思路，假设n=10, k=6, 我们来看数组：
a: {0, 1, 5, 3, 2, 2, 3, 0, 2, 6}
来看看计数过程：比如分数为0有2人，分数为4有0人：
通过计数，我们不仅考虑到了某分数值可能被多个人占据的情况，也考虑到了某分数值无人占据的情况，根据计数，可直接列出最后的结果，即数组b, 通过计数，实现了排序，时间复杂度为O(n).
下面，我们来看一下计数排序的程序：
using namespace std;// 0 <= a[i] <= k (其中i = 0, 1, 2,..., n-1)void countSort(int a[], int n, int k){int *c = new int[k + 1]; //用于计数int *b = new int[n]; //保存最终结果int i = 0;for(i = 0; i <= k; i++) // 初始化次数{c[i] = 0;}for(i = 0; i < n; i++) // 统计次数{c[a[i]]++;}for(i = 0; i <= k; i++){cout << c[i] << " ";}cout << endl;cout << c[0] << " ";for(i = 1; i <= k; i++) // 统计累计次数{c[i] += c[i - 1];cout << c[i] << " ";}cout << endl;for(i = 0; i < n; i++) // 根据计数，将a[i]放到对应的位置{b[--c[a[i]]] = a[i];}for(i = 0; i < n; i++){a[i] = b[i];}delete [] b;delete [] c;}int main(){int a[] = {0, 1, 5, 3, 2, 2, 3, 0, 2, 6};int n = 10;int k = 6;countSort(a, n, k);int i = 0;for(i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;return 0;}
结果：
2 1 3 2 0 1 1 （占据人数）
2 3 6 8 8 9 10 （累计人数）
0 0 1 2 2 2 3 3 5 6 (计数排序结果)
计数排序的思路很巧妙，需要好好领会。然而，计数排序也不是万能的，它有它的局限性：
a. 元素必须是非负整数
b. 必须知道数组元素的范围
曾经，参加过G公司和F公司的面试，两次都遇到了计数排序的身影。最后，我们再看T公司的一道面试题目：文件中有40亿个QQ号码，请对QQ号码进行去重，然后对去重后的QQ号码进行排序，内存要求是600M以内。
显然，这里可以用bitmap来做，把所有QQ号码记录到bitmap中，耗费内存512M，bitmap直接实现了去重的目的，然后从小到大输出，顺便就实现了排序。关于bitmap的相关知识，可以参考之前的文章：