计数排序算法初探

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

对于一个数组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
{5,3,2,6,3,8,2} {0,0,0,0,1,0,0,0}
{5,3,2,6,3,8,2} {0,0,1,0,0,0,0,0}
{5,3,2,6,3,8,2} {0,1,1,0,1,0,0,0}
{5,3,2,6,3,8,2} {0,1,1,0,1,1,0,0}
{5,3,2,6,3,8,2} {0,1,2,0,1,1,0,0}
{5,3,2,6,3,8,2} {0,1,2,0,1,1,0,1}
{5,3,2,6,3,8,2} {0,2,2,0,1,1,0,1}

每读取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.

《计数排序算法初探》上有2条评论

    1. 速度应该会快一点(但这种差距在今天的计算机上已经很难体现了),相比于需要多出比较才能排序的算法,计数排序只要几遍遍遍历就能排完了。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注