基数排序的进阶应用：对非负整数数组进行排序 题目描述 给定一个非负整数数组，要求使用基数排序（Radix Sort）算法对其进行升序排序。数组中的元素可能包含不同位数，例如 [170, 45, 75, 90, 2, 802, 24, 66] 。基数排序的核心思想是按数字的每一位（从最低位到最高位）进行稳定排序，最终实现整体有序。 解题过程 理解基数排序原理 基数排序不直接比较元素大小，而是将整数按位数切割成不同数字（如个位、十位、百位），依次对每位进行排序。 关键要求：每轮的排序必须是稳定的（即相同值的元素排序后相对顺序不变）。 常用稳定排序方法：计数排序（Counting Sort）。 确定最大数字的位数 遍历数组找到最大值 max_num ，例如 802 。 计算最大位数 max_digits ：通过不断除以10直到为0，统计次数。 示例中 max_digits = 3 （802有3位）。 从最低位到最高位逐轮排序 对每一位（从个位到最高位）执行计数排序： a. 创建长度为10的计数数组（对应数字0-9），统计当前位上每个数字的出现次数。 b. 将计数数组转换为前缀和形式，确定每个数字在输出数组中的最后位置。 c. 从原数组末尾向前遍历（保证稳定性），根据当前位数字放置到输出数组的对应位置。 d. 将输出数组复制回原数组，作为下一轮输入。 示例分步演示（以数组 [170, 45, 75, 90, 2, 802, 24, 66] 为例） 第一轮（个位） ： 按个位数字排序： 个位：0(170,90), 2(802,2), 4(24), 5(45,75), 6(66) 排序后： [170, 90, 802, 2, 24, 45, 75, 66] （稳定保持相同个位数的顺序）。 第二轮（十位） ： 按十位数字排序： 十位：0(802,2), 2(24), 4(45), 6(66), 7(170,75), 9(90) 排序后： [802, 2, 24, 45, 66, 170, 75, 90] 。 第三轮（百位） ： 按百位数字排序： 百位：0(2,24,45,66,75,90), 1(170), 8(802) 排序后： [2, 24, 45, 66, 75, 90, 170, 802] （最终有序）。 算法复杂度分析 时间复杂度：O(d·(n + k))，其中 d 为最大位数， k 为基数（10）， n 为元素个数。 空间复杂度：O(n + k)（用于计数数组和临时输出数组）。 关键点总结 基数排序适用于非负整数且位数差异不大的场景。 稳定性是保证排序正确性的核心，每轮需使用稳定排序方法（如计数排序）。 若存在负数，需先分离正负数并分别处理（或调整计数规则）。