计数排序及其应用例子
??? 计数排序法是一种简单的排序方法，这种排序算法对一个待排序的数组进行排序，并将排序结果放到另一个新的数组中。计数排序算法针对待排序数组中的每个记录，扫描待排序的数组一趟，统计待排序数组中有多少个记录的值比该记录的值小。假设针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序数组中的合适的存放位置即为c。
??? 假设有三个数组：
数组?A：待排序数组（非空，数据个数n）
数组?B：排序后的数组
数组?count：纪录A中某个数据在表B中的位置，初始值为0
对于A中某个数据Xi（0<=i<n），与表中各个数据Xj（0<=i<n）进行比较，记录下比Xi小的值的个数到count[i]。但是，我们发现，数据与自身的比较是多余的，而且当Xi与Xj比较后，就没有必要再比较Xj和Xi了。在此基础上我们对之前的操作方式进行一些变化。我们对A中的数据Xi与Xj进行比较，所不同的是Xj的j的范围为?i<j<=n?，即每个Xi只和其后的数据进行比较。在比较过程中，如果Xi?>?Xj?，则count[i]?=?count[i]+1；否则，count[j]=count[j]+1?。当算法完毕的时候，count数组中就记录了A中的各个数据在B中的实际位置。算法过程如下所示：?
n???0?????1?????2????3??/*数组的索引位置*/
A??21???32???17???21??/*数组中的数据*/
C???[0]??[0]??[0]??[0]??/*count的初始值*/
算法开始i=0，j取值{1?，2，3}。
（1）X0<X1?，所以count[1]+1
n???0?????1?????2????3??/*数组的索引位置*/
A??21???32???17???21??/*数组中的数据*/
C???[0]??[1]??[0]??[0]??/*count的值*/
（2）X0>X2?，所以count[0]+1
n???0?????1?????2????3??/*数组的索引位置*/
A??21???32???17???21??/*数组中的数据*/
C???[1]??[1]??[0]??[0]??/*count的值*/
（3）X0=X3?，所以count[3]+1
n???0?????1?????2????3??/*数组的索引位置*/
A??21???32???17???21??/*数组中的数据*/
C???[1]??[1]??[0]??[1]??/*count的值*/
接下来i=1?，j取值{2，3}
…….
如此继续直至算法完毕，则
n???0?????1?????2????3??/*数组的索引位置*/
A??21???32???17???21??/*数组中的数据*/
C???[1]??[3]??[0]??[2]??/*count的初始值*/
接下来的要做的只是按count中的值将A中的数据放到B中相应的位置上了，即?B[count[i]]?=?A[i]，则数组B中数据为
B?[17]?[21]?[21]?[32]
至此计数排序算法完成。
在上述过程中，我们看到，对于待排序数组中的相同数据，在排序后其先后顺序保持不变，也就是说以上原理的排序算法是一个稳定的排序算法。
算法复杂度：
????上述计数排序算法包含两重循环，假设数组A中的数据个数为n，那么在程序执行过程中，第二层循环控制变量j的执行次数随着第一层循环控制变量i的变化依次为n-1?，?n-2，n-3，…….，0?，这是一个差值为1的n项等差数列，所以第二层循环的执行次数为(n-1+0)*n/2,即n*（n-1）/2，所以该算法的时间复杂度为O（n2）。
?
在计数排序算法的代码中，我们假定输入是个数组A[0...n-1]，length[A]=n。另外还需要两个数组：存放排序结果的B[0...n-1]，以及提供临时存储区的C[0...k].
#include?<stdio.h>#include?<stdlib.h>#include?<iostream>using?namespace?std;void?CountSort(int?a[],?int?b[],int?k,int?num)
{
????int*?c?=?new?int[k+1];????for?(int?i=0;i<=k;i++)???????c[i]=0;????int?size?=?num;????for?(int?j=0;j<size;j++)???????c[a[j]]++;????//c[i]包含等于i的元素个数????for?(i=1;i<=k;i++)???????c[i]=c[i]+c[i-1];????//c[i]包含小于等于i的元素个数????for?(j=size-1;j>=0;j--)
????{????????b[c[a[j]]-1]=a[j];????????c[a[j]]--;
????}????????delete?[]?c;
}void?main(){????int?num,max;????cout<<"输入最大整数及输入个数"<<endl;????cin>>max;????cin>>num;????int*?a?=?new?int[num];????int*?b?=?new?int[num];????cout<<"排序前："<<endl;????for(int?i=0;i<num;i++)????{????????cin>>a[i];????????if?(a[i]>max)????????????i--;????}????????????CountSort(a,b,max,num);????cout<<"排序后："<<endl;????for?(int?j=0;j<num;j++)????{????????cout<<b[j]<<endl;????}????delete?[]?a;????delete?[]?b;}?
一个例子? form：http://zhedahht.blog.163.com/blog/static/25411174201131184017844/
?
题目：某公司有几万名员工，请完成一个时间复杂度为O(n)的算法对该公司员工的年龄作排序，可使用O(1)的辅助空间。
分析：排序是面试时经常被提及的一类题目，我们也熟悉其中很多种算法，诸如插入排序、归并排序、冒泡排序，快速排序等等。这些排序的算法，要么是O(n2)的，要么是O(nlogn)的。可是这道题竟然要求是O(n)的，这里面到底有什么玄机呢？
??? 题目特别强调是对一个公司的员工的年龄作排序。员工的数目虽然有几万人，但这几万员工的年龄却只有几十种可能。上班早的人一般也要等到将近二十岁才上班，一般人再晚到了六七十岁也不得不退休。
??? 由于年龄总共只有几十种可能，我们可以很方便地统计出每一个年龄里有多少名员工。举个简单的例子，假设总共有5个员工，他们的年龄分别是25、24、26、24、25。我们统计出他们的年龄，24岁的有两个，25岁的也有两个，26岁的一个。那么我们根据年龄排序的结果就是：24、24、25、25、26，即在表示年龄的数组里写出两个24、两个25和一个26。
??????????????? 想明白了这种思路，我们就可以写出如下代码：
void SortAges(int ages[], int length)
{
??? if(ages == NULL || length <= 0)
??????? return;
?
??? const int oldestAge = 99;
??? int timesOfAge[oldestAge + 1];
?
??? for(int i = 0; i <= oldestAge; ++ i)
??????? timesOfAge[i] = 0;
?
??? for(int i = 0; i < length; ++ i)
??? {
??????? int age = ages[i];
??????? if(age < 0 || age > oldestAge)
??????????? throw new std::exception("age out of range.");
?
??????? ++ timesOfAge[age];
??? }
?
??? int index = 0;
??? for(int i = 0; i <= oldestAge; ++ i)
??? {
??????? for(int j = 0; j < timesOfAge[i]; ++ j)
??????? {
??????????? ages[index] = i;
??????????? ++ index;
??????? }
??? }
}
?? 在上面的代码中，允许的范围是0到99岁。数组timesOfAge用来统计每个年龄出现的次数。某个年龄出现了多少次，就在数组ages里设置几次该年龄。这样就相当于给数组ages排序了。该方法用长度100的整数数组辅助空间换来了O(n)的时间效率。由于不管对多少人的年龄作排序，辅助数组的长度是固定的100个整数，因此它的空间复杂度是个常数，即O(1)。
????