基数排序
时间复杂度：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);
}
