专业微信网站开发公司,建设游戏网站需要哪些设备,做网页要花多少钱,网站如何做3d产品展示计数排序#xff08;Counting Sort#xff09;是一种非比较型排序算法#xff0c;适用于一定范围内的整数排序。它的基本思想是通过计数输入元素中每个值出现的次数#xff0c;然后计算每个值的起始位置#xff0c;最终将元素放到正确的位置上。计数排序的时间复杂度为 O(…计数排序Counting Sort是一种非比较型排序算法适用于一定范围内的整数排序。它的基本思想是通过计数输入元素中每个值出现的次数然后计算每个值的起始位置最终将元素放到正确的位置上。计数排序的时间复杂度为 O(n k)其中 n 是输入数组的长度k 是输入元素的范围。
以下是计数排序的 Java 实现
import java.util.Arrays; public class CountingSort { // 计数排序算法 public static void countingSort(int[] array) { if (array.length 0) { return; } // 找到数组中的最大值和最小值 int max array[0]; int min array[0]; for (int num : array) { if (num max) { max num; } if (num min) { min num; } } // 计算范围大小 int range max - min 1; // 创建计数数组并初始化 int[] countArray new int[range]; Arrays.fill(countArray, 0); // 统计每个元素出现的次数 for (int num : array) { countArray[num - min]; } // 计算每个元素在排序后数组中的位置 int index 0; for (int i 0; i countArray.length; i) { while (countArray[i] 0) { array[index] i min; countArray[i]--; } } } // 测试计数排序算法 public static void main(String[] args) { int[] array {4, 2, 2, 8, 3, 3, 1}; System.out.println(排序前: Arrays.toString(array)); countingSort(array); System.out.println(排序后: Arrays.toString(array)); }
}
代码说明 找到数组中的最大值和最小值遍历数组找到其中的最大值和最小值以便确定计数数组的范围。 创建计数数组根据最大值和最小值计算范围大小并创建计数数组。计数数组的长度为 max - min 1。 统计每个元素出现的次数遍历输入数组将每个元素减去最小值对应到计数数组的索引位置并增加计数。 计算每个元素在排序后数组中的位置遍历计数数组根据每个元素的计数将其在输入数组中的位置设置好。 测试代码在 main 方法中创建一个测试数组调用计数排序方法并输出排序前后的数组。
注意事项
计数排序适用于范围较小的整数排序对于范围很大的整数计数数组可能会占用过多内存。计数排序是稳定的排序算法即相同元素的相对位置在排序前后不会改变。
通过这种方法你可以高效地对特定范围内的整数进行排序。
