计数排序算法初探

计数排序是一种线性时间排序，相对于其他的排序算法（冒泡排序、快速排序），计数排序不是通过元素与元素之间的比较进行排序，而是通过计算来确定元素的位置。其具体的思路大致如下：

对于一个数组a[n]（这里采用C语言的定义方式，n代表数组长度），如果能够确定小于其中每个元素的元素的个数，那么元素的位置也就自然而然地确定了。例如，对于这样一个数组example[]={1,2,2,4,5,6}，其中小于等于元素1的元素数为1，那么1这个元素自然应该在example[]这个数组的第一个位置上。又如，小于等于2的元素个数有3个，那么有一个元素2应该被排在第三个位置上，另一个2则应该被排在前面即第二个位置上。也就是说，我们要实现计数排序算法，首先就应该统计出来每个元素在整个数组中出现了多少次。

对于这样一个数组{5,3,2,6,3,8,2}，我们去统计数组里元素的个数，并把它保存到一个数组里。这个数组的最大项是8，于是我们需要创建一个长度为8的数组，接着我们去遍历这个数组:

每读取a中的一个元素，在c数组中以该元素值为下标的值就加一。于是最后就得到了每个元素的个数。那么a中小于等于每个元素的元素个数，可以通过以下计算方法给出：

小于等于X的元素个数=X的个数 + (X-1)的个数

换句话说就是对计数进行累加。用这个公式去遍历一遍c数组，就可以得到c[]={0,2,4,4,5,6,6,7}，于是a中的2就应该放到第二位，三就应该放到第四位，但是我们还需要在第一位放一个2，第三位放一个3。这时，我们只需要每放一个数就将这个数对应的那个计数减去一。最后把a中的对应元素放到另一个保存输出的数组中，即可完成排序。

总结一下算法的实现步骤如下：

• 统计元素个数
• 累加计数来确定元素位置
• 每放一个数对应的计数建议
• 循环进行，直到排序结束

下面给出具体的代码（C语言），该代码在Win8.1+DevC++ 5.7.1环境下测试通过：

#include <stdio.h>

int main(int argc, char const *argv[])
{
	const int NUM=10;	//Define the array constant equals 10

	int input[NUM],output[NUM],temp[100];   //Define the necessary array
	for (int i = 0; i < NUM; ++i)
	{
		scanf("%d",&input[i]);		//Initialize the input array (Use the user input)
	}
	for (int j = 0; j < 100; ++j)
	{
		temp[j]=0;					//Initialize the temp array (Use 0)
	}
	for (int k = 0; k < NUM; ++k)
	{
		temp[input[k]]=temp[input[k]]+1;	//Traverse the array and calculate the numbers of every elements
	}
	for (int l = 1; l < 100; ++l)
	{
		temp[l]=temp[l]+temp[l-1];			//Count the number which less than every elements
	}
	for (int m = NUM-1; m >= 0; m--)
	{
		output[temp[input[m]]]=input[m];	//Export the result to the OUTPUT array
		temp[input[m]]=temp[input[m]]-1;
	}
	for (int n = 1; n <= NUM; ++n)
	{
		printf("%d\n",output[n] );		//Print all the array
	}
	return 0;
}

计数排序的一大缺陷就是，必须知道数组中最大元素的值，并且以这个值作为数组长度。虽然计数排序相对于其他比较类排序的时间复杂度较低，但是，在对于大数的排序中，需要占用大量的内存，而其中又很有可能出现很多浪费。所以，基于计数排序的基数排序就在一定程度上解决了这一问题。

在这里先开一个坑，基数排序的内容会在有空的时候填上。继续造轮子去了。

参考资料：

[1]Wikipedia,计数排序

[2]T.H.Cormen, C.E.Leiseron, R.L.Revest, C.Stein——算法导论,108-109.