用c++写一个链式基数排序

下面是一个用 C++ 实现链式基数排序的示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 定义链表节点结构体
struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// 获取数字 num 在第 k 位上的数值
int getDigit(int num, int k) {
    while (k > 1) {
        num /= 10;
        k--;
    }
    return num % 10;
}

// 链式基数排序
void radixSort(vector<int>& nums) {
    // 创建 10 个桶
    vector<Node*> buckets(10, nullptr);

    // 获取最大数字的位数
    int maxNum = *max_element(nums.begin(), nums.end());
    int maxDigit = 0;
    while (maxNum > 0) {
        maxNum /= 10;
        maxDigit++;
    }

    // 依次比较每一位上的数值
    for (int k = 1; k <= maxDigit; k++) {
        // 将数字放入对应的桶中
        for (int n : nums) {
            int digit = getDigit(n, k);
            Node* node = new Node(n);
            if (buckets[digit] == nullptr) {
                buckets[digit] = node;
            } else {
                Node* cur = buckets[digit];
                while (cur->next != nullptr) {
                    cur = cur->next;
                }
                cur->next = node;
            }
        }

        // 重新排列原数组
        int idx = 0;
        for (Node* bucket : buckets) {
            while (bucket != nullptr) {
                nums[idx++] = bucket->val;
                bucket = bucket->next;
            }
        }

        // 清空桶
        for (int i = 0; i < 10; i++) {
            buckets[i] = nullptr;
        }
    }
}

// 测试代码
int main() {
    vector<int> nums = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(nums);
    for (int n : nums) {
        cout << n << " ";
    }
    cout << endl;
    return 0;
}

该代码首先定义了一个链表节点结构体，用于存储每个数字。然后实现了一个 getDigit 函数，用于获取数字在指定位数上的数值。接着是链式基数排序函数 radixSort，该函数依次比较每一位上的数值，将数字放入对应的桶中，然后按照桶的顺序重新排列原数组。最后是一个测试代码，用于验证排序结果的正确性。