计数排序是一种非比较的排序，这种方法思路大概是先算出待排序数据里面的数字分别出现多少次，然后再依据这个存放进新的数组里面，输出这个数组，排序也就完成了。时间复杂度为o(n+k)，很多人说是o(n)，但其实只是接近而已。其中里面的n是排序的数据个数，而k是排序中最大的值，可想而知，在n确定的情况下，k的值越小，时间复杂度越低，例如就算n很小，但排序数是｛2，5，3，10000｝的话，那也需要很多时间，此排序方法就不怎么适用了。
程序例子：（主要参考排序核心方法，其他的写得不够好）
<pre><code>
include <iostream>
using namespace std;
//-------------------------
int data[100];//全局变量，用来存放待排序数据
int array_length;//数组的长度
int array_max;//数组中最大的值，也就是k
//---------------------------------
//初始化数组
void Init_array()
{
cout<<"Input:(End with 1000)";
for(int i=0;; i++)
{
cin>>data[i];
if(data[i]==1000)
{
array_length = i;//由此获得数组长度
break;
}
}
}
//-----------------------------------
//求数组中最大的数
void max_array()
{
int t;
array_max = data[0];
for(int i=0; i<array_length-1; ++i)
{
if(data[i]<data[i+1])
{
array_max = data[i+1];
}
else
{
t = data[i];
data[i] = data[i+1];
data[i+1] = t;
}
}
}
//----------------------------------
//计数排序
//参数分别是1.待排序数组，2.数组长度，3.待排序数组中最大的值，也就是k
void sort_counter(int d[], int n, int k)
{
int i, j = 0,p = 0;
// 实际需要的空间比K大1
k++;
//辅助数组，当然也可以用其他编程技术来代替
int counter[100] = {0};
// 计数
for(i=0; i<n; ++i)
{
p = d[i];
counter[d[i]]++; //counter数组下标为排序的数，下标对应的数组值为这个数出现的次数
}
//将计数结果保存到待排数据数组
for(i=0; i<k; ++i)
{
while(counter[i]-- > 0) //将出现的数字以及次数，依次放到数组中
{
d[j++] = i;
}
}
}
//主函数
int main(void)
{
Init_array();
max_array();
sort_counter(data, array_length-1, array_max);
int i;
for(i=0; i<array_length; ++i)
{
cout<<data[i]<<" ";
}
cout<<endl;
return 0;
}
</code></pre>
