首页 > 代码库 > 计数排序算法

计数排序算法

基本思想

统计数组data,小于data[i]的个数为N,则把data[i]放在第N+1个位置上面。

实用范围:

所有数都在[0,max]范围内,max为数组的最大值,适用于max不是很大的情况。

对于数据2 5 3 0 2 3 0 3程序执行的过程如下图所示:





C++代码:


#include <iostream>
using namespace std;
namespace mysort
{//找出数组中的最大值
	int Max(int * data, int len)
	{
		int ret = -1;
		for (int i = 0; i < len; i++)
			if (data[i]>ret)
				ret = data[i];
		return ret;
	}
	void sort(int *data, int len)
	{
		int max = Max(data, len);
		int *c = new int[max+1];
		int *ret = new int[len];		
		memset((void*)c, 0, sizeof(int)* (max + 1));
		for (int i = 0; i < len; ++i) c[data[i]]++;//统计每个数出现的次数
		for (int i = 0; i < max; i++) c[i + 1] += c[i];//统计小于某个数出现的次数
		for (int i = len - 1; i >= 0; i--)
		{
			ret[ c[ data[i] ] - 1 ] = data[i];
			--c[data[i]];
		}
		memcpy((void*)data, (void*)ret, sizeof(int)*len);
	}
};
int main()
{
	//计数排序的前提是,所有数都在[0,max]范围内,适用于数组最大值不是很大的情况。
	int a[] = { 0, 4, 3, 1, 2, 3, 4, 5, 6, 4, 3, 2 };
	mysort::sort(a, 12);
	return 0;
}

总结:计数排序和通常的交换排不同,它直接将待排序的数放在了排序后正确的位置。算法虽然有O(N)的时间和空间复杂度,但它的使用范围有一定的局限性。算法思路和用位向量排序(《编程珠玑》第一章)有相似之处。

Key Word:不同问题,不同的分析。