基数排序

1.基数排序的思想

• 针对于有多个关键字的排序算法。先按照一个关键字进行排序，完成后在按另一个关键字排序。先按照权重小关键字排序，在按照权重大的关键字排序。
• 按照每个关键字的值的范围，定义上相同数量的队列。对于数字我们先按照个位进行排序，然后在按照十位排。

2.基数排序的实现

// 获取最大数据的位数
int GetDigit(int *arr, int len)
{
	int max = arr[0];
	for (int i = 0; i < len; ++i)
	{
		if (max < arr[i]) max = arr[i];
	}
	
	int digit = 0;
	while (max) // max 1234 123 12 1 0
	{
		digit++;
		max /= 10;
	}
	
	return digit;
}

// 时间复杂度： O(d*n)
// 空间复杂度： O(n)
// 稳定性： 稳定
// 获取一个数据相应位数上的值
int GetRadix(int val, int digit)
{
	// val 1234
	int radix = val % 10; // 4
	while (digit)
	{
		val /= 10; // 123
		radix = val % 10; // 3
		digit--;
	}
	
	return radix;
}

void RadixSort(int *arr, int len)
{
	int maxDigit = GetDigit(arr, len);
	
	ListQue que[10];
	for (int i = 0; i < 10; ++i)
	{
		InitListQue(&que[i]);
	}
	
	// 根据不同的位数，处理整个数据
	for (int i = 0; i < maxDigit; ++i)
	{
		// 将arr中的所有数据取其i这个位数的值， 并且插入到相应值的队列中
		for (int j = 0; j < len; ++j)
		{
			int radix = GetRadix(arr[j], i);
			Push(&que[radix], arr[j]);
		}
		
		// 将所有队列按照从前到后的顺序把值全部出到arr中。
		int index = 0;
		for (int k = 0; k < 10; ++k)
		{
			while (!Empty(&que[k]))
			{
				GetHead(&que[k], &arr[index++]);
				Pop(&que[k]);
			}
		}
	}
	
	for (int i = 0; i < 10; ++i)
	{
		DestroyListQue(&que[i]);
	}
}