sort/基数排序.cpp

10.基数排序

10.1 描述
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高
优先级高的在前，高优先级相同的低优先级高的在前。

10.2 复杂程度
时间复杂度O(n*k)                 
空间复杂度O(n+k)

10.3 代码
#include<stdio.h>
#include<string.h>
#define N 14	//数组长度
#define D 14	//最大位数

int GetDigit(int M, int i) //取整数M的第i位数
{
	while(i > 1)
	{
		M /= 10;
		i--;
	}
	return M % 10;
}

void RadixSort(int num[], int len)
{
	int i, j, k, l, digit;
	int allot[10][N];	//《分配数组》

	memset(allot, 0, sizeof(allot));//初始化《分配数组》

	for(i = 1; i <= D; i++)
	{
		//分配相应位数的数据，并存入《分配数组》
		for(j = 0; j < len; j++)	
		{			
			digit = GetDigit(num[j], i);
			k = 0;
			while(allot[digit][k])
				k++;
			allot[digit][k] = num[j];
		}
		//将《分配数组》的数据依次收集到原数组中
		l = 0; 
		for(j = 0; j < 10; j++)	
		{	
			k = 0;
			while(allot[j][k] > 0)
			{
				num[l++] = allot[j][k];
				k++;
			}
		}
		//每次分配，收集后初始化《分配数组》，用于下一位数的分配和收集
		memset(allot, 0, sizeof(allot));
	}
}

int main()
{
	int num[N] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};

	RadixSort(num, N);

	for(int i = 0; i < N; i++)
		printf("%d ", num[i]);
	printf("\n");
	return 0;
}

10.4 运行时间
0.02213s