////////////////////////////////////////////////////
//递归:RadixSort()公有成员函数
//采用MSD方法实现基数排序,left->right是排序的范围,
//d是表示采用第d位为基准进行排序
//算法的思想:利用优先级高的关键码i对序列进行分组,
//每个分组内都具有相同的关键码k,所有的关键码为k的元素
//都处于一个桶内,关键码k对应桶的大小放在BucketStart[k]
////////////////////////////////////////////////////
template<class T,class E>
void DataSortList<T,E>::RadixSort(int left,int right,int d)
{
    /*递归结束的条件*/
    if(left>=right||d<=0)
        return;
    int L=right-left+1;             //得到当前待排序序列长度
    /*首先按照关键码的第d位进行桶的划分*/
    int count[10];                  //数组:用于存放十个阿拉伯数字对应的桶的大小
    for(int i=0;i<10;i++)           //把count[]数组全部初始化为0
        count[i]=0;
    for(i=0;i<L;i++)                //统计每个字符对应的桶的大小
    {
        int k=getDigit(Vector[i],d);//获取第i个元素的第d个排序码k
        count[k]++;                 //统计d位置上排序码为k的元素的个数
    };

    /*把count[]数组中数据转换成每个桶开始的位置*/
    int start=0;                    //每个桶的开始位置
    int len;                        //当前处理的前个桶的长度
    int Bucketstart[10];            //记录每个桶的开始位置
    for(i=0;i<10;i++)               
    {
        len=count[i];               //记录下当前桶的长度
        count[i]=start;             //数据的替换
        Bucketstart[i]=start;
        start=len+start;            //计算下个桶的开始位置
    };

    /*把Vector[]中的数据以桶序放入辅助数组Arr*/
    Element<T,E>* Arr=              //开辟辅助数组的存储空间
        new Element<T,E>[L];
    for(i=0;i<L;i++)
    {
        int k=getDigit(Vector[i],d);//取出要进行比较的关键码
        int pos=count[k];           //得到要插入元素在桶中的位置
        Arr[pos]=Vector[i];         //把元素插入其中
        count[k]++;
    };

    /*把辅助数组中的元素复制回原来的Vector[]中*/
    for(i=0;i<L;i++)
        Vector[i]=Arr[i];

    /*对每个桶(子序列)再进行递归排序*/
    for(i=0;i<10;i++)
    {
        int p1=Bucketstart[i];      //当前桶的开始位置
        int p2=count[i+1]-1;        //当前桶的结束位置
        RadixSort(p1,p2,d-1);
    };
};
/////////////////////////////RadixSort()公有函数结束

发觉这样的排序好象时间复杂消耗在getdigit()函数上比较多,虽然从表面
上看时间复杂度不错.