一、算法简介
基数排序（Radix Sort）是一种非比较型的排序算法，适用于待排序元素为非负整数的情况。它根据元素的位数（基数）进行排序，在每一位上对元素进行稳定的排序，最终得到有序序列。
基数排序的基本思想是，按照个位、十位、百位等依次对待排序元素进行排序。首先将待排序元素按照个位数的大小分配到09的桶中，然后按照桶的顺序依次取出元素得到一个新的序列；接着根据十位数的大小再次分配到09的桶中，再次按照桶的顺序取出元素进行排序。直到最高位排序完成，整个序列就变成了一个有序序列。
基数排序的时间复杂度为 O(d*(n+k))，其中 d 是最大元素的位数，n 是待排序元素的数量，k 是基数的大小（例如十进制中的k=10）。由于基数排序是非比较型的排序算法，它不受元素的大小关系影响，因此可以在某些情况下具有较好的性能。
二、算法实现
下面是基数排序的C#实现示例：
public static void RadixSort(int[] array) { int n = array.Length; if (n <= 1) { return; } // 找到最大值 int maxVal = array[0]; for (int i = 1; i < n; i++) { if (array[i] > maxVal) { maxVal = array[i]; } } // 按照个位、十位、百位...进行排序 for (int exp = 1; maxVal / exp > 0; exp *= 10) { CountingSortByDigit(array, n, exp); } } private static void CountingSortByDigit(int[] array, int n, int exp) { int[] output = new int[n]; int[] count = new int[10]; // 0~9 // 统计待排序元素出现的次数 for (int i = 0; i < n; i++) { count[(array[i] / exp) % 10]++; } // 计算每个元素在有序排列中的最后一个位置的索引 for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } // 从后向前遍历待排序数组，根据每个元素的位数信息放入输出数组 for (int i = n - 1; i >= 0; i--) { output[count[(array[i] / exp) % 10] - 1] = array[i]; count[(array[i] / exp) % 10]--; } // 将排序好的结果复制回原始数组 for (int i = 0; i < n; i++) { array[i] = output[i]; } }
调用示例：
int[] array = { 170, 45, 75, 90, 802, 24, 2, 66 }; RadixSort(array); Console.WriteLine("排序后的数组："); foreach (int element in array) { Console.Write(element + " "); }
以上是基数排序的一个示例实现。在这个示例中，我们首先找到待排序数组中的最大值，以确定需要排序的位数。然后按照每一位的大小进行稳定的计数排序，通过不断更新count数组来计算每个元素在有序排列中的最后一个位置的索引。接着，根据位数信息将元素放入输出数组，最后将排序好的结果复制回原始数组。
需要注意的是，在应用基数排序时，需要根据待排序元素的特性确定排序位数，并确保待排序元素都是非负整数或可映射到非负整数范围内。如果待排序元素不满足这个要求，就需要进行适当的映射转换，才能使用基数排序算法。
