对0到n^2-1范围内的数字进行排序，要求时间复杂度为O(n)。
可以直接采用基数排序法对其排序，但是这些数字为已知范围，所以有更进一步的优化，即将所有的数字转换成n进制，这样这些数在n进制下只有两位，即只需要比较2O(n)即可。转换成n进制消耗2O(n)，所以对于比较的数字为四位以上时，该算法较普通的基数排序有优势。
具体代码如下：
修改：此处的插入排序应该改为计数排序。因为插入排序时间复杂度太高
//习题 8.3-4采用改进的基数排序，所选择的稳定的排序算法为插入排序。
//对所要比较的数进行转换，对于范围从0到n^2-1的数字，将所有元素转换成n进制
//此时只需比较两位。当比较的数字位数比较多时时间效率比较高。
#include<iostream>
using namespace std;
//使用插入排序作为稳定的排序算法
//******************
//******************
//*******************
void Insert_sort(int a[],int (*b)[2],int n,int length)
{
int i,j,key;
for(i=1;i<length;i++)
{
key=b[i][n];
j=i-1;
while(key<b[j][n])
{
int temp;
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
temp=b[j+1][0];
b[j+1][0]=b[j][0];
b[j][0]=temp;
temp=b[j+1][1];
b[j+1][1]=b[j][1];
b[j][1]=temp;
j=j-1;
if(j<0)
{
break;
}
}
}
}
//**********
//***********
//**********
//将数组中的数转换成n进制，这样只需要比较两位即可。
void Divide(int a[],int (*b)[2],int n,int length)
{
int i,j;
int c[100]={0};
for(i=0;i<length;i++)
{
c[i]=a[i];
}
for(i=0;i<length;i++)
{
//b[i][0]存放低位
b[i][0]=c[i]%n;
//b[i][1]存放高位
b[i][1]=c[i]/n;
}
}
void RadixSort(int a[],int (*b)[2],int n,int length)
{
int i;
Divide(a,b,n,length);
for(i=0;i<=1;i++)
{
Insert_sort(a,b,i,length);
}
}
int main()
{
int a[10],b[10][2];
int i;
for(i=0;i<10;i++)
{
a[i]=rand()%100000;
cout<<a[i]<< ' ';
}
cout<<endl;
RadixSort(a,b,1000,10);
for(i=0;i<10;i++)
{
cout<<a[i]<<' ';
}
cout<<endl;
}