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

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

#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 个桶和一个 Collect 桶
    vector<Node*> buckets(11, 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;
            }
        }

        // 收集 Collect 桶中的数字
        int idx = 0;
        if (buckets[10] != nullptr) {
            Node* cur = buckets[10];
            while (cur != nullptr) {
                nums[idx++] = cur->val;
                cur = cur->next;
            }
        }

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

        // 清空 Collect 桶
        buckets[10] = nullptr;

        // 将数字放入 Collect 桶中
        for (int n : nums) {
            if (n < 0) {
                Node* node = new Node(n);
                if (buckets[10] == nullptr) {
                    buckets[10] = node;
                } else {
                    Node* cur = buckets[10];
                    while (cur->next != nullptr) {
                        cur = cur->next;
                    }
                    cur->next = node;
                }
            }
        }

        // 清空原数组中的负数
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0) {
                nums[i] = 0;
            }
        }
    }
}

// 测试代码
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;
}

该代码与前面的实现基本相同，只是额外添加了一个 Collect 桶和一些额外的操作。在每次排序时，将原数组中的负数放入 Collect 桶中，然后清空原数组中的负数。在重新排列原数组时，先将 Collect 桶中的数字放入原数组中的前面位置，然后再按照桶的顺序重新排列原数组。最后，清空 Collect 桶。该实现支持对负数的排序。