数据结构与算法 - 基数排序

基数排序

基数排序是一种非比较型整数排序算法,其原理是将数据按位数切割成不同的数字,然后按每个位数分别比较。

假设说,我们要对 100 万个手机号码进行排序,应该选择什么排序算法呢?排的快的有归并、快排时间复杂度是 \(O(n \log n)\),计数排序和桶排序虽然更快一些,但是手机号码位数是11位,那得需要多少桶?内存条表示不服。

这个时候,我们使用基数排序是最好的选择。

数据结构与算法 - 基数排序

我们以[ 892, 846, 821, 199, 810,700 ]这组数字来做例子演示。

首先,创建十个桶,用来辅助排序。

数据结构与算法 - 基数排序

先排个位数,根据个位数的值将数据放到对应下标值的桶中。

数据结构与算法 - 基数排序

排完后,我们将桶中的数据依次取出。

数据结构与算法 - 基数排序

那么接下来,我们排十位数。

数据结构与算法 - 基数排序

最后,排百位数。

数据结构与算法 - 基数排序

排序完成。

代码实现

基数排序可以看成桶排序的扩展,也是用桶来辅助排序,代码如下:

void sort(vector<int> arr)
{
    int length = arr.size();

    int max = arr[0];
    for(int i = 0; i < length; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }

    // 当前排序位置
    int location = 1;

    // 桶列表
    vector<vector<int>> bucketList(10);

    while(true) {
        // 判断是否排完
        int dd = (int)pow(10, location-1);
        if(max < dd) {
            break;
        }

        // 数据入桶
        for(int i = 0; i < length; i++) {
            int number = (arr[i]/dd) % 10;
            bucketList[i].push_back(arr[i]);
        }

        // 写回数组
        int nn = 0;
        for(int i=0; i < 10; i++) {
            int size = bucketList[i].size();
            for(int ii=0; ii < size; ii++) {
                arr[nn++] = bucketList[i][ii];
            }
            bucketList[i].clear();
        }
        location++;
    }
}

其实它的思想很简单,不管你的数字有多大,按照一位一位的排,0 - 9 最多也就十个桶:先按权重小的位置排序,然后按权重大的位置排序。

当然,如果你有需求,也可以选择从高位往低位排。

上一篇:1038 统计同成绩学生 (20 分)


下一篇:数组