计数排序不同于比较排序，是基于计数的方式，对于计数排序，假设每一个输入都是介于0~k之间的整数。对于每一个输入元素x，确定出小于x的元素的个数。假如有17个元素小于x，则x就属于第18个输出位置。 计数排序涉及到三个数组A[0…..length-1],length为数组A的长度；数组B与数组A长度相等，存放最终排序的结果；C[0…..K]存放A中每个元素的个数，k为数组A中的最大值。 int count_k(int A[],int length)，此函数为了确定数组A中最大的元素，用来确定C数组的长度。 计数排序的实现： [img]http://files.jb51.net/file_images/article/201604/201604121155551.jpg[/img]

count_sort(A,B,k);

k=5

for(j=0;j<=length-1;j++)//计算A中元素的个数    
C[A[j]] = C[A[j]]+1;

表示数组A中有2个0、0个1、2个2、3个3、0个4、1个5 [img]http://files.jb51.net/file_images/article/201604/201604121155562.jpg[/img]

  for(i=1;i<=k;i++)//计算小于等于C[i]的元素的个数    
C[i] = C[i] + C[i-1];

小于等于0的数有两个，小于等于1的数有两个、小于等于2的数有4个、小于等于3的有7个、小于等于4的有7个、小于等于5的有8个 [img]http://files.jb51.net/file_images/article/201604/201604121155563.jpg[/img] for循环分析如下 j=7;A[j]=A[7]=3;C[A[j]]=C[3]=7;C[A[j]]-1=6;B[C[A[j]]-1]=B[6]=A[j]=3;C[A[j]]=C[A[j]]-1=6 [img]http://files.jb51.net/file_images/article/201604/201604121155574.jpg[/img]   j=6;A[j]=A[6]=0;C[A[j]]=C[0]=2;C[A[j]]-1=1;B[C[A[j]]-1]=B[1]=A[j]=0;C[A[j]]=C[A[j]]-1=1 [img]http://files.jb51.net/file_images/article/201604/201604121155575.jpg[/img]   j=5;A[j]=A[5]=3;C[A[j]]=C[3]=6;C[A[j]]-1=5;B[C[A[j]]-1]=B[5]=A[j]=3;C[A[j]]=C[A[j]]-1=5; [img]http://files.jb51.net/file_images/article/201604/201604121155576.jpg[/img]   j=4;A[j]=A[4]=2;C[A[j]]=C[2]=4;C[A[j]]-1=3;B[C[A[j]]-1]=B[3]=A[j]=2;C[A[j]]=C[A[j]]-1=3; [img]http://files.jb51.net/file_images/article/201604/201604121155587.jpg[/img]   j=3;A[j]=A[3]=0;C[A[j]]=C[0]=1;C[A[j]]-1=0;B[C[A[j]]-1]=B[0]=A[j]=0;C[A[j]]=C[A[j]]-1=0; [img]http://files.jb51.net/file_images/article/201604/201604121155588.jpg[/img]   j=2;A[j]=A[2]=3;C[A[j]]=C[3]=5;C[A[j]]-1=4;B[C[A[j]]-1]=B[4]=A[j]=3;C[A[j]]=C[A[j]]-1=4; [img]http://files.jb51.net/file_images/article/201604/201604121155589.jpg[/img]   j=1;A[j]=A[1]=5;C[A[j]]=C[5]=8;C[A[j]]-1=7;B[C[A[j]]-1]=B[7]=A[j]=5;C[A[j]]=C[A[j]]-1=7; [img]http://files.jb51.net/file_images/article/201604/2016041211555810.jpg[/img]   j=0;A[j]=A[0]=2;C[A[j]]=C[2]=3;C[A[j]]-1=2;B[C[A[j]]-1]=B[2]=A[j]=2;C[A[j]]=C[A[j]]-1=2; [img]http://files.jb51.net/file_images/article/201604/2016041211555911.jpg[/img]   计数排序的最后运行截图 [img]http://files.jb51.net/file_images/article/201604/2016041211555912.png[/img]   计数排序分析：j=length-1;j>=0;j–此处为倒序，是为了保证排序的稳定性，这个在基数排序中有重要的作用。