用 c++实现基数排序

以下是用 C++ 实现基数排序的示例代码：

#include <iostream>
#include <vector>

// 获取一个数字的某一位数，从低位开始计算，index 从 0 开始
int getDigit(int num, int index) {
    for (int i = 0; i < index; i++) {
        num /= 10;
    }
    return num % 10;
}

void radixSort(std::vector<int>& nums) {
    // 先找到最大的数字，确定需要比较的位数
    int maxNum = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > maxNum) {
            maxNum = nums[i];
        }
    }
    int maxDigit = 0;
    while (maxNum) {
        maxDigit++;
        maxNum /= 10;
    }

    // 对每一位进行计数排序
    std::vector<int> count(10, 0);
    std::vector<int> temp(nums.size());
    for (int i = 0; i < maxDigit; i++) {
        // 统计每个数字出现的次数
        for (int j = 0; j < nums.size(); j++) {
            int digit = getDigit(nums[j], i);
            count[digit]++;
        }
        // 将每个桶内的数字按顺序放入临时数组中
        int sum = 0;
        for (int j = 0; j < 10; j++) {
            int numCount = count[j];
            count[j] = sum;
            sum += numCount;
        }
        for (int j = 0; j < nums.size(); j++) {
            int digit = getDigit(nums[j], i);
            temp[count[digit]] = nums[j];
            count[digit]++;
        }
        // 将临时数组中的数字复制回原数组中
        for (int j = 0; j < nums.size(); j++) {
            nums[j] = temp[j];
        }
        // 清空计数数组
        for (int j = 0; j < 10; j++) {
            count[j] = 0;
        }
    }
}

int main() {
    std::vector<int> nums = { 53, 3, 542, 748, 14, 214, 154, 63, 616 };
    radixSort(nums);
    for (int i = 0; i < nums.size(); i++) {
        std::cout << nums[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

该实现中，`getDigit` 函数用于获取一个数字的某一位数，然后在 `radixSort` 函数中，先找到最大的数字，确定需要比较的位数，然后对每一位进行计数排序，最终得到有序的结果。