【算法导论】基数排序

基数排序

时间复杂度：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];
	}
}

注意：我是在vs2008上运行的，与vc 6.0有点区别，主要是循环体中的循环变量的作用域，出错体现在循环变量的重复定义上。例如：在vs2008或vs2010上，程序为：

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为：

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
}　

原文：http://blog.csdn.net/tengweitw/article/details/9670303

作者：nineheadedbird