基数排序的核心思路是将整数按位数切割成不同的数字，然后按每个位数分别比较。它从最低位开始排序，依次到最高位，经过多轮分配和收集后，整个序列就会变为有序状态，不需要像快速排序、归并排序那样进行元素间的直接比较。
基数排序的实现原理
基数排序的实现主要依赖两个核心操作：分配和收集。分配是指将待排序的元素按照当前位的数值放入对应的桶中，收集则是将桶中的元素按顺序取出，组成新的序列。具体步骤如下：
- 找到待排序序列中的最大数，确定最大数的位数，也就是需要排序的轮数
- 从最低位（个位）开始，对每一位进行分配和收集操作
- 每一位处理完成后，得到的序列就是该位有序的结果，处理完最高位后整个序列有序
C#实现基数排序的完整代码
下面是使用C#编写的基数排序完整实现，包含辅助方法和排序主逻辑，代码中添加了详细的中文注释说明每一步的作用：
using System;
using System.Collections.Generic;
using System.Linq;
public class RadixSortHelper
{
/// <summary>
/// 基数排序主方法
/// </summary>
/// <param name="arr">待排序的整数数组</param>
/// <returns>排序后的数组</returns>
public static int[] RadixSort(int[] arr)
{
if (arr == null || arr.Length <= 1)
{
return arr;
}
// 找到数组中的最大值，确定最大位数
int max = arr.Max();
int maxDigit = 0;
while (max > 0)
{
maxDigit++;
max /= 10;
}
// 从最低位开始，逐位排序
for (int digit = 1; digit <= maxDigit; digit++)
{
// 创建10个桶，对应0-9的数字
List<List<int>> buckets = new List<List<int>>();
for (int i = 0; i < 10; i++)
{
buckets.Add(new List<int>());
}
// 分配：将元素按当前位的数值放入对应桶中
foreach (int num in arr)
{
int currentDigitValue = GetDigitValue(num, digit);
buckets[currentDigitValue].Add(num);
}
// 收集：将桶中的元素按顺序取出，组成新的数组
int index = 0;
foreach (List<int> bucket in buckets)
{
foreach (int num in bucket)
{
arr[index] = num;
index++;
}
}
}
return arr;
}
/// <summary>
/// 获取数字指定位数的数值，从个位开始为第1位
/// </summary>
/// <param name="num">目标数字</param>
/// <param name="digit">位数，1代表个位</param>
/// <returns>指定位数的数值</returns>
private static int GetDigitValue(int num, int digit)
{
return (num / (int)Math.Pow(10, digit - 1)) % 10;
}
}
// 测试代码
class Program
{
static void Main(string[] args)
{
int[] testArr = { 170, 45, 75, 90, 802, 24, 2, 66 };
Console.WriteLine("排序前的数组：");
Console.WriteLine(string.Join(", ", testArr));
int[] sortedArr = RadixSortHelper.RadixSort(testArr);
Console.WriteLine("排序后的数组：");
Console.WriteLine(string.Join(", ", sortedArr));
}
}
算法特性分析
时间复杂度
基数排序的时间复杂度为O(k*n)，其中n是待排序元素的数量，k是最大数的位数。当k较小时，基数排序的效率会非常高，远优于比较型排序算法的O(n log n)复杂度。
空间复杂度
基数排序需要额外的空间存储桶，空间复杂度为O(n+k)，k为桶的数量，这里固定为10，所以空间复杂度可以近似看作O(n)。
适用场景
基数排序只适用于整数或者可以转换为整数的数据类型排序，尤其适合位数不多、数值范围集中的整数序列排序，比如手机号排序、身份证号排序等场景。如果待排序的元素包含负数或者非整数类型，需要先做额外的处理才能使用基数排序。
实现注意事项
- 如果待排序数组包含负数，需要先区分正数和负数，分别排序后再合并，或者先对负数取绝对值排序，再调整符号
- GetDigitValue方法中使用
Math.Pow计算位权，需要注意整数除法的特性，避免计算错误 - 桶的初始化每次循环都要重新创建，确保每一轮排序的桶都是空的，不会残留上一轮的数据