1. 基数排序原理图解
基数排序是一种非比较的排序算法，其核心思想是通过将整数按位数切割成不同的数字，然后按每个位数分别比较。具体步骤如下：
1. 确定最大值：找到数组中的最大值，以确定需要处理的位数。
2. 分配到桶中：从最低位（个位）开始，根据当前位的数字将元素分配到10个桶中（0-9）。
3. 收集元素：按顺序从桶中收集元素，形成新的数组。
4. 重复处理：对更高位（十位、百位等）重复步骤2和3，直到处理完所有位数。
图解示例：
假设数组为 `[170, 45, 75, 90, 802, 24, 2, 66]`。
1. **初始状态**：`[170, 45, 75, 90, 802, 24, 2, 66]`
2. **处理个位**：
- 将元素按个位分配到桶中：
- 桶0: `170, 90`
- 桶2: `802, 2`
- 桶4: `24`
- 桶5: `45`
- 桶6: `66`
- 桶7: `75`
- 收集后数组：`[170, 90, 802, 2, 24, 45, 66, 75]`
3. **处理十位**：
- 将元素按十位分配到桶中：
- 桶0: `802, 2, 170`
- 桶4: `24`
- 桶5: `45`
- 桶6: `66`
- 桶7: `75`
- 桶9: `90`
- 收集后数组：`[802, 2, 170, 24, 45, 66, 75, 90]`
4. **处理百位**：
- 将元素按百位分配到桶中：
- 桶0: `170, 2, 24, 45, 66, 75, 90`
- 桶8: `802`
- 收集后数组：`[2, 24, 45, 66, 75, 90, 170, 802]`
2. Java代码实现及注释
```java
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(array);
System.out.println("排序后的数组：");
System.out.println(Arrays.toString(array));
}
// 基数排序方法
public static void radixSort(int[] arr) {
// 找到数组中的最大值，确定位数
int max = Arrays.stream(arr).max().getAsInt();
int exp = 1; // 位数（个位、十位、百位等）
while (max / exp > 0) {
// 创建10个桶
int[][] buckets = new int[10][arr.length];
int[] bucketCounts = new int[10];
// 将元素分配到桶中
for (int num : arr) {
int index = (num / exp) % 10;
buckets[index][bucketCounts[index]] = num;
bucketCounts[index]++;
}
// 从桶中收集元素
int idx = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < bucketCounts[i]; j++) {
arr[idx++] = buckets[i][j];
}
}
// 移动到位处理更高位
exp *= 10;
}
}
}
```
3. 代码说明
1. 确定最大值：
- 通过 `Arrays.stream(arr).max().getAsInt()` 找到数组中的最大值。
2. 分配到桶中：
- 使用 `int[][] buckets` 创建10个桶。
- 根据当前位的数字将元素分配到相应的桶中。
3. 收集元素：
- 按顺序从桶中收集元素，重新填充数组。
4. 时间复杂度：
- **最坏情况**：`O(nk)`，其中 `n` 是元素个数，`k` 是位数。
- **平均情况**：`O(nk)`。
- **最好情况**：`O(nk)`。
5. 空间复杂度：
- `O(n + k)`，其中 `n` 是元素个数，`k` 是桶的数量（10）。
6. 稳定性：
- 基数排序是**稳定的**，因为相同值的元素在分配和收集过程中保持相对顺序。
4. 应用场景
1. 整数排序：
- 基数排序适合对整数进行排序，特别是当整数的范围较大时。
2. 字符串排序：
- 可以扩展基数排序对字符串进行排序，通过逐字符处理。
3. 大数据排序：
- 对于大数据集，基数排序可以与其他排序算法结合使用，提高性能。
4. 教学和演示：
- 基数排序的实现简单，适合用于教学和算法演示。
5. 总结
基数排序是一种高效的非比较排序算法，特别适合对整数和字符串进行排序。它的优点是时间复杂度低，且稳定性好。然而，基数排序的空间复杂度较高，需要额外的存储空间来存储桶。在实际应用中，基数排序通常用于处理大规模数据集或与其他排序算法结合使用，以提高整体性能。