C++实现基数排序算法示例，结合“学生成绩排名”的生活场景，帮助理解非比较排序的原理。代码包含详细注释和分步解析：

---

生活场景：考试成绩排序

假设需要将某班级学生的考试成绩从低到高排序：

1. 成绩范围：0-100分的整数
2. 特殊要求：不使用比较操作，直接根据数字特征排序
3. 排序策略：按个位、十位依次分类排序

---

C++代码实现（LSD基数排序）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 获取数字的某一位（digit=0表示个位，digit=1表示十位）
int getDigit(int number, int digit) {
    int divisor = 1;
    for (int i = 0; i < digit; ++i) {
        divisor *= 10;
    }
    return (number / divisor) % 10;
}

// 基数排序主函数
void radixSort(vector<int>& scores) {
    const int MAX_DIGITS = 3; // 成绩最多3位数（0-100）
    queue<int> buckets[10];   // 0-9号数字桶

    // 从低位到高位依次排序
    for (int d = 0; d < MAX_DIGITS; ++d) {
        // 将数字分配到桶中
        for (int score : scores) {
            int digitVal = getDigit(score, d);
            buckets[digitVal].push(score);
        }

        // 从桶中收集数字
        int index = 0;
        for (int b = 0; b < 10; ++b) {
            while (!buckets[b].empty()) {
                scores[index++] = buckets[b].front();
                buckets[b].pop();
            }
        }

        // 打印当前排序过程（可选）
        cout << "第" << d+1 << "轮排序结果：";
        for (int s : scores) cout << s << " ";
        cout << endl;
    }
}

int main() {
    vector<int> testScores = {78, 5, 92, 67, 100, 42, 33, 89, 15, 70};

    cout << "原始成绩：";
    for (int s : testScores) cout << s << " ";
    cout << "\n\n开始基数排序：" << endl;

    radixSort(testScores);

    cout << "\n最终排序结果：";
    for (int s : testScores) cout << s << " ";

    return 0;
}

---

执行结果

原始成绩：78 5 92 67 100 42 33 89 15 70 

开始基数排序：
第1轮排序结果：70 100 92 42 33 5 15 67 78 89 
第2轮排序结果：100 5 15 33 42 67 70 78 89 92 
第3轮排序结果：5 15 33 42 67 70 78 89 92 100 

最终排序结果：5 15 33 42 67 70 78 89 92 100 

---

算法原理图解（分位排序过程）

初始数据：78, 5, 92, 67, 100, 42, 33, 89, 15, 70

第1轮（个位排序）：

按个位分配桶：
0: 70, 100
2: 92
5: 5
7: 67
8: 78
9: 89
收集结果：70 100 92 5 67 78 89 ...（其他桶为空）

第2轮（十位排序）：

按十位分配桶：
0: 100, 5
1: 15
3: 33
4: 42
6: 67, 70
7: 78
8: 89
9: 92
收集结果：100 5 15 33 42 67 70 78 89 92

第3轮（百位排序）：

按百位分配桶：
0: 5,15,33,42,67,70,78,89,92 
1: 100
收集结果：5 15 33 42 67 70 78 89 92 100

---

关键概念解析（学生成绩比喻）

编程术语	成绩排序比喻	技术说明
数字分桶	按成绩的个位/十位分组	根据特定位数值分类
低位优先	先比较个位再比较十位	LSD（Least Significant Digit）策略
队列桶	临时存放同数字的成绩组	保持同组内原有顺序
稳定性	同数字成绩保持输入顺序	保证排序稳定性的关键

---

算法特性分析

特性	说明
时间复杂度	O(kn) → k为最大数字位数
空间复杂度	O(n + b) → b为基数（这里b=10）
优势	非比较排序，适合范围有限整数
适用场景	手机号排序、身份证号排序

---

扩展练习建议

1. 处理负数
   增加符号位处理：

   // 分离正负数，分别排序后合并
   vector<int> negatives, positives;
   

2. 优化空间使用
   使用计数排序代替队列桶：

   vector<int> count(10, 0); // 计数每个桶的元素数量
   

3. 支持更大数字
   动态计算最大位数：

   int maxNum = *max_element(scores.begin(), scores.end());
   int maxDigits = to_string(maxNum).length();
   

通过这个实现，可以深入理解非比较排序的独特优势。就像老师快速整理答题卡，基数排序通过巧妙的数字分桶策略，无需直接比较元素即可完成高效排序。这是处理大数据量整数排序的重要工具！