计数排序
计数排序（Counting Sort）是一种非比较型的整数排序算法，其主要优点在于对于一定范围内的整数排序非常高效，时间复杂度可以达到
基本思想
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
代码实现
查看代码
java
public class CountingSort {
// 计数排序函数
public static void countingSort(int[] arr) {
// 找出最大值和最小值
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
// 初始化计数数组
int[] count = new int[range];
// 统计每个元素的出现次数
for (int value : arr) {
count[value - min]++;
}
// 累加计数数组
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 创建输出数组
int[] output = new int[arr.length];
// 根据计数数组将元素放到正确的位置
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
// 将输出数组的内容复制回原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}
// 打印数组的方法
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
// 主函数
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
System.out.println("原始数组:");
printArray(arr);
countingSort(arr);
System.out.println("排序后的数组:");
printArray(arr);
}
}代码解释
- 寻找最大值和最小值：通过
Arrays.stream(arr).max().getAsInt()和Arrays.stream(arr).min().getAsInt()找出数组中的最大值和最小值。 - 初始化计数数组：根据最大值和最小值之间的范围，初始化一个计数数组
count。 - 统计元素出现次数：遍历待排序数组，对于每个元素，在计数数组相应的位置上加 1。
- 累加计数数组：遍历计数数组，将
count[i]的值加上count[i-1]的值，这样修改后的count数组中的count[i]就表示小于等于i的所有元素的数量。 - 构建输出数组：从后往前遍历待排序数组，对于每个元素，根据它的值找到它在输出数组中的位置（即
count数组对应索引的值减去 1），然后将该元素放入输出数组中的这个位置，并将count数组对应索引的值减去 1。 - 复制结果：将排序后的数组
output复制回原数组arr。