Python版本

a = [100,82,6,33,84,28,41,64,89,61]

def radix_sort(a):
    max_len = len(str( max(a) ))
    #位循环，反向循环
    for i in range(-1, -max_len-1, -1):
        b = []
        #建桶
        bucket = [[] for i in range(10)]
        #进桶
        for j in a :
            try:
                radix = int(str(j)[i])
            except:
                radix = 0
            bucket[radix].append(j)

        #出桶操作
        for k in range(10):
            if len(bucket[k]) > 0:
                b.extend(bucket[k]) # a = a + b 列表相加 


        a = b
    return a

print(radix_sort(a))

C++版本

算法思路

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按位进行排序。这里是LSD（Least Significant Digit，最低有效位）排序方式：

• 找出数组中最大数，确定最大位数
• 从最低位开始到最高位依次进行排序
• 对每一位数字进行分桶： 1、创建10个桶（队列），对应0-9 2、根据当前位的数字将元素放入对应的桶中
• 按顺序从各个桶中取出元素，形成新的序列
• 重复这个过程直到处理完所有位数

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

// 打印数组
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 获取数字特定位置上的数字
int getDigit(int number, int position) {
    return (int)(number / pow(10, position)) % 10;
}

// 基数排序
std::vector<int> radixSort(std::vector<int>& arr) {
    // 找出最大值，确定最大位数
    int maxVal = *std::max_element(arr.begin(), arr.end());
    int maxDigits = 0;
    while (maxVal > 0) {
        maxDigits++;
        maxVal /= 10;
    }

    // 使用队列进行基数排序
    for (int digit = 0; digit < maxDigits; ++digit) {
        // 创建10个桶
        std::vector<std::queue<int>> buckets(10);

        // 将元素分配到相应桶中
        for (int num : arr) {
            int currentDigit = getDigit(num, digit);
            buckets[currentDigit].push(num);
        }

        // 从桶中取出元素放回原数组
        int index = 0;
        for (int i = 0; i < 10; ++i) {
            while (!buckets[i].empty()) {
                arr[index++] = buckets[i].front();
                buckets[i].pop();
            }
        }

        std::cout << "After sorting by digit " << digit << ": ";
        printArray(arr);
    }

    return arr;
}

int main() {
    std::vector<int> a = {100, 82, 6, 33, 84, 28, 41, 64, 89, 61};

    std::cout << "Original array: ";
    printArray(a);

    std::vector<int> sorted = radixSort(a);

    std::cout << "Sorted array: ";
    printArray(sorted);

    return 0;
}

基数排序的时间复杂度为：O(k·n)

其中：

n 是待排序元素的个数 k 是数字的最大位数（或者说最大关键字长度）

具体分析：

确定最大值位数：需要遍历数组一次，时间复杂度为 O(n) 对每一位进行排序： 每次分配元素到桶中：O(n) 每次从桶中收集元素：O(n) 总共对 k 位进行处理，所以总时间为 O(k·n) 优点：当 k 接近常数时（比如固定位数的整数），基数排序可以接近线性时间复杂度 O(n)，在大规模数据排序中具有优势。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com