基数排序
一句话总结
基数排序是 计数排序 的扩展，对整数的每一位依次进行稳定排序，最终完成整体排序。
核心要点
1. 基数排序的本质
- 基数（Radix）即进制，适用于整数或可转换整数的数据
- 是计数排序的扩展，用于解决计数排序空间复杂度过高的问题
- 与桶排序关系不大
2. 稳定排序的必要性
- 对每一位排序时必须使用稳定排序
- 原因：相同高位或低位的值需要保持原有相对顺序
- 示例：56 和 57，十位数相同（都是5），稳定排序保证个位数顺序不变
3. 排序顺序
- 从低位（个位）到高位依次排序
- 由于使用稳定排序，低位排序的结果不会被高位排序破坏
基本原理
示例：对 nums = [329, 457, 839, 439, 720, 355, 350] 进行基数排序
初始状态：
329
457
839
439
720
355
350
按个位数稳定排序后：
720
350
355
457
329
839
439
按十位数稳定排序后：
720
329
839
439
350
355
457
按百位数稳定排序后（最终结果）：
329
350
355
439
457
720
839
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 基数排序 | O(d * (n + k)) | d 为最大数字位数，n 为元素个数，k 为基数（如十进制 k=10） |
| 每一位计数排序 | O(n + k) | 每一位的排序使用计数排序 |
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 912. 排序数组 | 中等 |
相关概念
相关实体
- labuladong：算法学习网站及作者
总结
基数排序通过将整数按位分解，利用计数排序的稳定性，从低位到高位依次排序，最终完成整体排序。关键在于每一位的排序必须是稳定的。
待补充
由于原文通过 JavaScript 动态加载，无法完整获取，以下内容缺失：
- 完整的代码实现
- 如何处理不同位数（如数组中有2位数和4位数）
- 如何处理负数
- 是否可以从高位到低位排序的讨论
- 空间复杂度分析
- 算法可视化代码的详细解释