在排序算法的大家族中，基数排序凭借其独特的排序思路和应用场景，占据着不可或缺的位置。今天，就让我们一同深入探索基数排序的奥秘。
一、基数排序的核心思想
基数排序是一种非比较型整数排序算法，它的核心在于按位排序。与基于元素比较的排序算法不同，基数排序将整数按位数切割成不同的数字，然后从最低位开始，依次对每一位进行排序，直到最高位处理完毕，最终得到一个有序的数列。
举个简单的例子，假设有一组数字 [329, 457, 657, 839, 436, 720, 355]。首先，我们关注个位数字，将这些数字按照个位数字进行排序，得到 [720, 436, 355, 457, 657, 329, 839]。接着，对十位数字进行排序，结果变为 [720, 329, 436, 839, 355, 457, 657]。最后，按百位数字排序，得到最终的有序序列 [329, 355, 436, 457, 657, 720, 839]。每一位的排序就像是一场筛选，逐步将所有数字排列整齐。
二、基数排序的实现步骤
- 确定排序的位数：首先要找出待排序数组中最大的数，从而确定需要排序的最大位数。比如上述例子中最大数是 839，所以最大位数是 3 位。
- 从最低位开始排序：使用一种稳定的排序算法（如计数排序）对每一位进行排序。以计数排序为例，创建一个计数数组，统计每个数字在当前位上出现的次数，然后根据计数数组重新排列原数组中的元素。
- 重复步骤：依次对每一位进行排序，直到最高位完成排序，此时整个数组就有序了。
下面是使用 Java 实现基数排序的代码示例：
public class RadixSort {
public static void radixSort(int[] arr) {
// 找到最大数，确定最大位数
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// 从个位开始，对每一位进行排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}
private static void countSort(int[] arr, int exp) {
int[] output = new int[arr.length];
int[] count = new int[10];
// 统计每个数字在当前位上出现的次数
for (int num : arr) {
count[(num / exp) % 10]++;
}
// 计算累计计数，确定每个数字在输出数组中的位置
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 根据计数数组，将原数组中的元素放入输出数组
for (int i = arr.length - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// 将输出数组复制回原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}
public static void main(String[] args) {
int[] arr = {329, 457, 657, 839, 436, 720, 355};
System.out.println("排序前数组: " + java.util.Arrays.toString(arr));
radixSort(arr);
System.out.println("排序后数组: " + java.util.Arrays.toString(arr));
}
}三、基数排序的时间和空间复杂度
- 时间复杂度：基数排序的时间复杂度为 O(d(n + k))，其中 d 是最大数字的位数，n 是数列元素个数，k 是每一位的取值范围（如十进制中 k =10）。当数字位数 d 和取值范围 k 相对稳定时，基数排序的时间复杂度接近线性，在处理大规模数据时表现出色。
- 空间复杂度：基数排序需要额外的空间来存储临时数据，如计数数组和输出数组，所以空间复杂度为 O(n + k) 。
四、基数排序的稳定性
基数排序是稳定的排序算法。在每一位的排序过程中，使用的稳定排序算法（如计数排序）确保了相等元素的相对顺序不会改变。这使得基数排序在一些对元素相对顺序有要求的场景中具有优势，比如在对学生成绩进行排序时，成绩相同的学生希望保持原来的顺序。
五、基数排序的应用场景
- 整数排序：由于基数排序针对整数按位排序的特性，非常适合对整数数组进行排序，尤其是在数字范围不是特别大且位数相对固定的情况下，效率极高。
- 字符串排序：通过将字符串看作字符的序列，也可以应用基数排序的思想进行排序。比如对一系列长度相同的单词按照字典序排序，就可以从字符串的最后一个字符开始，逐位进行排序。
六、总结
基数排序以其独特的按位排序方式，为我们提供了一种高效的排序解决方案。它在时间复杂度和稳定性方面的特点，使其在特定场景下能够发挥出巨大的优势。与其他排序算法相比，基数排序的思想独树一帜，为我们解决排序问题提供了新的思路。在实际应用中，我们可以根据数据的特点和需求，灵活选择合适的排序算法，让程序的性能得到最优发挥。
