【算法导论】基数排序

时间复杂度：$O(n)$.

基本思路：两个数比较大小，我们的直观感觉是先比较高位，若相同则比较低位。但是这样做需要记录额外的数据，浪费空间。而基数排序则是先比较低位，再比较高位。通过各个位的比较进行排序，如果数组元素最大有$N$位，则总共需要$N$次排序。注意：按位排序必须是稳定排序（两个相等的数其在序列的前后位置顺序，在排序前后不改变），所以在这我选择了计数排序。

具体操作见下图：

​

具体实现如下：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

void CountSort(int* arrayA,int* arrayD,int n,int k);
void RadixSort(int* arrayA,int n);

void main()
{
	int arrayD[]={1046,2084,9046,12074,56,7026,8099,17059,33,1};
	int n=sizeof(arrayD)/sizeof(int);
	RadixSort(arrayD,n);

	for(int i=0;i<n;i++)
		printf("%d ",arrayD[i]);
	printf("\n");

}

/****************************************\
函数功能：进行非比较的计数排序
输入：数组D为原始数组
输出：无
\****************************************/
void RadixSort(int* arrayD,int n)
{
	int base=1;//用于取出各个位
	int* arrayA=(int*)malloc(sizeof(int)*n);
	for(int k=0;k<5;k++)//这里的5由原始数组最大数据位数确定
	{	
		base*=10;
		for(int i=0;i<n;i++)//这里用来取各个位上的数
		{
			arrayA[i]=arrayD[i]%base;
			arrayA[i]/=base/10;
		}
		CountSort(arrayA,arrayD,n,10);
	}
	free(arrayA);//记得释放空间
}

/****************************************\
函数功能：进行非比较的计数排序
输入：数组A、D，D为原始数组
输出：无
\****************************************/
void CountSort(int* arrayA,int*arrayD,int n,int k)
{
	int* arrayB=(int*)malloc(sizeof(int)*n);
	int* arrayC=(int*)malloc(sizeof(int)*k);

	for(int i=0;i<=k;i++)
		arrayC[i]=0;//数组C初始化
	for(int j=0;j<n;j++)
		arrayC[arrayA[j]]=arrayC[arrayA[j]]+1;
	for(int i=1;i<=k;i++)
		arrayC[i]=arrayC[i]+arrayC[i-1];//得到各个元素的位置
	
	for(int j=n-1;j>=0;j--)
	{
		arrayB[arrayC[arrayA[j]]-1]=arrayD[j];
		arrayC[arrayA[j]]=arrayC[arrayA[j]]-1;//进行计数排序
	}
	for(int i=0;i<n;i++)
	{
		arrayD[i]=arrayB[i];
	}
}