基数排序（Radix Sort） 题目描述：给定一个非负整数数组，要求使用基数排序算法将其按升序排列。要求时间复杂度为O(n* k)，其中n是数组长度，k是数字的最大位数。 解题过程： 理解基数排序的基本思想 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行比较排序。从最低有效位（个位）开始，到最高有效位结束。 算法步骤详解 步骤1：找到数组中的最大值，确定需要排序的轮数（最大位数） 遍历数组找到最大值 计算最大值的位数，这决定了需要多少轮排序 步骤2：从最低位开始，对每一位进行稳定排序 使用计数排序作为子排序算法 从个位开始，然后是十位、百位，直到最高位 每一轮排序都必须是稳定的（相同值的相对位置不变） 步骤3：具体实现过程 a) 初始化10个桶（0-9） b) 对于每一位： 将数字按照当前位的值分配到对应的桶中 按桶的顺序（0-9）依次取出数字 用取出的数字更新原数组 示例演示 以数组[ 170, 45, 75, 90, 2, 802, 24, 66 ]为例： 第一轮（按个位排序）： 桶0: 170, 90 桶2: 2, 802 桶4: 24 桶5: 45, 75 桶6: 66 排序后：[ 170, 90, 2, 802, 24, 45, 75, 66 ] 第二轮（按十位排序）： 桶0: 2, 802 桶2: 24 桶4: 45 桶6: 66 桶7: 170, 75 桶9: 90 排序后：[ 2, 802, 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(n* k)，其中k是最大位数 空间复杂度：O(n + 10)（需要额外的桶空间） 特殊情况处理 数字位数不同时，高位补0处理 负数需要特殊处理（本题限定为非负整数）