基数排序
基数排序是一种非比较排序算法，它按照数字的位数进行排序，从最低位到最高位逐位进行稳定的排序操作。它适用于整数排序，特别是当数字位数较少时效率很高。
算法原理
基数排序的基本思想是：按照数字的位数进行排序，从最低位（个位）开始，对每一位进行稳定的排序（通常使用计数排序）。经过对所有位数的排序后，整个数组就排好序了。
算法步骤
- 找到数组中最大的数，确定最大位数
- 从最低位（个位）开始，对每一位进行稳定的排序
- 对每一位使用计数排序或其他稳定排序算法
- 重复上述步骤，直到处理完所有位数
时间复杂度
- 最坏情况：O(d × (n + k))，其中 d 是最大位数，n 是元素个数，k 是基数（通常为10）
- 平均情况：O(d × (n + k))
- 最好情况：O(d × (n + k))
空间复杂度
O(n + k) - 基数排序需要额外的空间来存储临时数组。
稳定性
基数排序是稳定的排序算法，相等元素的相对顺序不会改变。
适用场景
- 整数排序，特别是数字位数较少的情况
- 需要稳定排序的场景
- 对时间复杂度有要求的排序
优缺点
- 优点：时间复杂度为 O(d × (n + k))，在数字位数较少时效率很高；稳定排序
- 缺点：需要额外的空间；只适用于整数排序；当数字位数很多时效率低