基数排序¶

把数据从数组里一个个复制到链表里，然后从链表里一个个复制到数组里。不断的重复，来回复制。

优点：算法简单数组复制到链表链表复制到数组，来来回回复制。效率很高。速度很高。

缺点：需要多一倍的存储空间（需要二倍的空间，数组和链表的空间）。

基数¶

十进制的基数是10，二进制的基数是2。扑克牌排序：四种花色基数是4，13种牌基数是13。

排序¶

示例

未排数组：421 240 035 532 305 430 124

按个位排：（240 430）（421）（532）（124）（035 305）

按十位排：（305）（421 124) (430 532 035) (240)

按百位排：（035）（124）（240）（305）（421 430）（532）

MSD（先排最高位，最高位优先）、LSD（最低位优先）

设计算法的时候用链表去做。

十进制所以需要10个链表。基数是几就需要几个链表。

首先按照个位排放到链表里然后从链表里拿出来

个位是0的排前面个位是1的在后面，越大越在后面。并且个位是0的是一组。

然后按照十位放到链表里再拿出来
最后按照百位放到链表里再拿出来
等等以此类推。

原始数据从数组里拿出来，放到链表里，从链表里复制出来，再放到数组里。

数组到链表，链表到数组，反复进行。排序就完成了。

代码示例¶

1、先判断最大的数有几位¶

int maxdigit(int data[], int n)
{
    int d = 1;
    int p = 10;
    for (int i = 0; i < n; ++i) {
        while (data[i] >= p) { //大于10有2位，大于100有3位。等等
            p*=10;
            ++d;
        }
    }
    return d;
}

2、最大数有几位就循环几次（按照个位排，按照十位排，...）。¶

排序算法：（按照最低位优先，先排最低位。个位、十位、百位...）

再有一个循环所有的数，进行排序判断放哪个链表（桶）内：

把一个个数从数组里放到链表里。

判断个位的话，根据个位数是几，放到哪个链表里。如果是9就放到9的链表里。如果是8就放到8的链表里。

判断十位的话，根据十位数是几，放到哪个链表里。

再循环所有的链表（桶），把链表里的数再放回数组里。

把每一个链表里的数依次拿出来，放到数组里：如果链表不是空的，就一直取数据，取了再把它删除。

void radixsort(int data[], int n)
{
    //n：数组里有多少数
    int digits = maxdigit(data, n);
    //基数是几就需要几个链表
    list<int> lists[10];
    int d,j,k,factor;
    //最大的数有几位 就循环几次 factor提取个位十位百位
    for (d = 1, factor = 1; d <= digits; factor*=10, d++) {
        for (j = 0; j < n; j++) {
            //把所有的数循环一遍，然后放到对应的链表里
            lists[(data[j] / factor) % 10].push_back(data[j]);
        }
        for (j = k = 0; j < 10; j++) {
            //把每一个数从各个链表里放回到数组里
            while (!lists[j].empty()) {
                data[k++] = lists[j].front();//取链表开头的数据
                lists[j].pop_front();//取完就把数据从链表删除
            }
        }


//        //查看中间结果 按个位排序 按十位排序 等等
//        for (int m = 0; m < n; m++) {
//            cout << data[m] << " ";
//        }
//        cout << endl;
    }
}

调试

//测试
void test()
{
    int data[10] = {179, 208, 306, 93, 859, 984, 55, 9, 271, 33};
    radixsort(data, 10);
    //排序后的结果
    for (int i = 0; i < 10; i++) {
        cout << data[i] << " ";
    }
    cout << endl;
}