常见排序算法之计数排序与基数排序

1.计数排序

顾名思义，是对待排序数组中的数据进行统计，然后根据统计的数据进行排序，例如：

待排序数组：

a[] = { 100, 123, 112, 123, 201, 123, 112, 156, 156, 178, 185, 156, 123, 112 }

首先取出数组中最大值与最小值（这个不用说了吧）

最大值：201  最小值：100

因此该数组的数值范围为 201 - 100 + 1 = 102

开辟一个大小为102的数组 count[102] 并将所有元素初始化为0

再次遍历数组，以 a[ i - 100 ] 作为数组count的下标，对该项进行加1

得到的count数组应该是（这里count元素为0的项就不出现了，太多了）

count[ 0 ] = 1

count[ 12 ] = 3

count[ 23 ] = 4

count[ 56 ] = 3

count[ 78 ] = 1

count[ 85 ] = 1

count[ 101 ] = 1

其余的元素都为0

此时遍历count数组，将每个元素对应写回a数组，此时数组a应该为

a = { 100,112,112,112,123,123,123,123,156,156,156,178,185,201 }

可以看到，数组a已经排好了序。

代码如下：

void CountSort(int* a, size_t n)  //计数排序
{
	assert(a);
	int min = a[0];
	int max = a[0];
	for (int i = 1; i < n; ++i)
	{
		if (a[i] > max)
			max = a[i];
		else if (a[i] < min)
			min = a[i];
	}

	int countNum = max - min + 1;
	int* countArray = new int[countNum];
	memset(countArray, 0, sizeof(int)*(countNum));
	for (int i = 0; i < n; ++i)
	{
		++countArray[a[i] - min];
	}

	int index = 0;
	for (int i = 0; i < countNum; ++i)  //写回数组
	{
		while (countArray[i]--)
		{
			a[index++] = i + min;
		}
	}

	delete[] countArray;
}

可以看到，计数排序有很大的局限性，它适合对数据范围相对比较集中的数据集合进行排序。

2.基数排序

我们通过一个例子来看基数排序是怎样进行排序的

设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}

我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。

所以我们不妨把0~9视为10个桶。 

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。

分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。

这时，得到的序列就是个位数上呈递增趋势的序列。 

按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}

接着按照十位进行如上排序（注意：没有十位的数按照十位为0处理）

按照十位数排序： {0, 100, 2, 11, 123, 30, 543, 49, 50, 187}

接着按照百位进行如上排序（注意：没有百位的数按照百位为0处理）

按照百位数排序： {0, 2, 11, 30, 49, 50, 100, 123, 187, 543}

排序完成

代码如下：

int GetMaxBit(int* a, size_t n)  //获取数组中数字最多的位
{
	assert(a);

	int BitNum = 1;
	int tmpData = 10;
	for (int i = 0; i < n; ++i)
	{
		while (tmpData <= a[i])
		{
			++BitNum;
			tmpData *= 10;
		}
	}
	return BitNum;
}

void RadixSort(int* a, size_t n)  //基数排序
{
	assert(a);
	
	int maxBit = GetMaxBit(a, n);
	int digit = 1;
	int* tmp = new int[n];
	int countBit[10];  //计数
	int startBit[10];  //起始位置
	for (int i = 1; i <= maxBit; ++i)
	{
		memset(countBit, 0, sizeof(int)* 10);
		for (int i = 0; i < n; ++i)
		{
			int bit = (a[i]/digit)%10;  //先各位，在十位百位……
			++countBit[bit];
		}

		memset(startBit, 0, sizeof(int)* 10);
		startBit[0] = 0;
		for (int i = 1; i < 10; ++i)
		{
			startBit[i] = startBit[i - 1] + countBit[i - 1];
		}

		for (int i = 0; i < n; ++i)  //存入临时数组
		{
			int index = startBit[(a[i]/digit)%10]++;
			tmp[index] = a[i];
		}

		for (int i = 0; i < n; ++i)  //写回原数组
		{
			a[i] = tmp[i];
		}

		digit *= 10;
	}
	
	delete[] tmp;
}