常見排序算法之計(jì)數(shù)排序與基數(shù)排序

1.計(jì)數(shù)排序

顧名思義，是對(duì)待排序數(shù)組中的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，然后根據(jù)統(tǒng)計(jì)的數(shù)據(jù)進(jìn)行排序，例如：

待排序數(shù)組：

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

首先取出數(shù)組中最大值與最小值（這個(gè)不用說了吧）

最大值：201  最小值：100

因此該數(shù)組的數(shù)值范圍為 201 - 100 + 1 = 102

開辟一個(gè)大小為102的數(shù)組 count[102] 并將所有元素初始化為0

再次遍歷數(shù)組，以 a[ i - 100 ] 作為數(shù)組count的下標(biāo)，對(duì)該項(xiàng)進(jìn)行加1

得到的count數(shù)組應(yīng)該是（這里count元素為0的項(xiàng)就不出現(xiàn)了，太多了）

count[ 0 ] = 1

count[ 12 ] = 3

count[ 23 ] = 4

count[ 56 ] = 3

count[ 78 ] = 1

count[ 85 ] = 1

count[ 101 ] = 1

其余的元素都為0

此時(shí)遍歷count數(shù)組，將每個(gè)元素對(duì)應(yīng)寫回a數(shù)組，此時(shí)數(shù)組a應(yīng)該為

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

可以看到，數(shù)組a已經(jīng)排好了序。

代碼如下：

void CountSort(int* a, size_t n)  //計(jì)數(shù)排序
{
	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)  //寫回?cái)?shù)組
	{
		while (countArray[i]--)
		{
			a[index++] = i + min;
		}
	}

	delete[] countArray;
}

可以看到，計(jì)數(shù)排序有很大的局限性，它適合對(duì)數(shù)據(jù)范圍相對(duì)比較集中的數(shù)據(jù)集合進(jìn)行排序。

2.基數(shù)排序

我們通過一個(gè)例子來看基數(shù)排序是怎樣進(jìn)行排序的

設(shè)有一個(gè)初始序列為: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}

我們知道，任何一個(gè)阿拉伯?dāng)?shù)，它的各個(gè)位數(shù)上的基數(shù)都是以0~9來表示的。

所以我們不妨把0~9視為10個(gè)桶。 

我們先根據(jù)序列的個(gè)位數(shù)的數(shù)字來進(jìn)行分類，將其分到指定的桶中。例如：R[0] = 50，個(gè)位數(shù)上是0，將這個(gè)數(shù)存入編號(hào)為0的桶中。

分類后，我們?cè)趶母鱾€(gè)桶中，將這些數(shù)按照從編號(hào)0到編號(hào)9的順序依次將所有數(shù)取出來。

這時(shí)，得到的序列就是個(gè)位數(shù)上呈遞增趨勢(shì)的序列。 

按照個(gè)位數(shù)排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}

接著按照十位進(jìn)行如上排序（注意：沒有十位的數(shù)按照十位為0處理）

按照十位數(shù)排序： {0, 100, 2, 11, 123, 30, 543, 49, 50, 187}

接著按照百位進(jìn)行如上排序（注意：沒有百位的數(shù)按照百位為0處理）

按照百位數(shù)排序： {0, 2, 11, 30, 49, 50, 100, 123, 187, 543}

排序完成

代碼如下：

int GetMaxBit(int* a, size_t n)  //獲取數(shù)組中數(shù)字最多的位
{
	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)  //基數(shù)排序
{
	assert(a);
	
	int maxBit = GetMaxBit(a, n);
	int digit = 1;
	int* tmp = new int[n];
	int countBit[10];  //計(jì)數(shù)
	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)  //存入臨時(shí)數(shù)組
		{
			int index = startBit[(a[i]/digit)%10]++;
			tmp[index] = a[i];
		}

		for (int i = 0; i < n; ++i)  //寫回原數(shù)組
		{
			a[i] = tmp[i];
		}

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