犧牲空間換時(shí)間的非比較排序之計(jì)數(shù)排序和基數(shù)排序

非比較排序試用于元素比較集中的序列。

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

1. 找出待排序的數(shù)組中最大和最小的元素

2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)

3. 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）

4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

void CountSort(int *a, int size)
{
	assert(a);
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < size; i++)
	{
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}
	int CountSize = max - min + 1;//該序列的范圍在min~max之間，所以開(kāi)辟max-min+1
	int *CountArray = new int[CountSize];
	memset(CountArray,0,CountSize*sizeof(int));
	for (int i = 0; i < size; i++)
	{
		CountArray[a[i]-min]++;//比如序列在1萬(wàn)到2萬(wàn)之間，那么1萬(wàn)應(yīng)該存在下標(biāo)為0的數(shù)組上
	}
	int index = 0;
	for (int i = 0; i <= CountSize; i++)
	{
		int count = CountArray[i];
		while (count-- > 0)
		{
			a[index++] = i+ min;//那么此時(shí)下標(biāo)為0的數(shù)，就是1萬(wàn)
		}
	}
}

2、基數(shù)排序

  基數(shù)排序指的是先把序列中的每個(gè)數(shù)中的個(gè)位排序，然后十位排序，直到超過(guò)序列中最大數(shù)的位數(shù)

void DigitSort(int *a, int size)
{
	assert(a);
	int bit = 1, sum = 10;
	for (int i = 0; i < size; i++)
	{

		while (a[i] >= sum)   //取最大數(shù)的位數(shù)
		{
			bit++;
			sum *= 10;
		}
	}
	int digit = 1;
	int *bucket = new int[size];
	while (digit <= bit)
	{
		int count[10] = { 0 };
		int position[10] = { 0 };
		for (int i = 0; i < size; i++)
		{
			int numbit = pow(10,digit-1);
			int bitvalue = (a[i] / numbit) % 10;
			count[bitvalue]++;  
		}
		for (int i = 1; i < 10; i++)
		{
			position[i] = position[i - 1] + count[i - 1];
		}
		for (int i = 0; i < size; i++)
		{
			int numbit = pow(10, digit - 1);
			int bitvalue = (a[i] / numbit) % 10;
			bucket[position[bitvalue]++] = a[i];
		}
		digit++;      
		memcpy(a,bucket,size*sizeof(int));
	}
}