品牌网站建设堅持大蝌蚪,开发一个网站要多久,织梦网站模板响应式,怎样做展示型网站计数排序#xff08;Counting Sort#xff09;是一种非比较型的排序算法#xff0c;它通过统计每个元素的出现频率#xff0c;然后计算元素的位置信息#xff0c;最后将元素放到正确的位置#xff0c;从而实现排序。计数排序特别适用于元素范围有限的情况#xff0c;比如…计数排序Counting Sort是一种非比较型的排序算法它通过统计每个元素的出现频率然后计算元素的位置信息最后将元素放到正确的位置从而实现排序。计数排序特别适用于元素范围有限的情况比如整数的范围较小。
算法思想
计数排序的基本思想是
确定范围找出待排序数据的最小值和最大值。计数创建一个计数数组用来统计每个元素出现的次数。累积将计数数组中的计数值累积以确定每个元素的最终位置。排序根据累积的计数信息将元素放到正确的位置。
过程示例
假设有一个待排序的数组[4, 2, 2, 8, 3, 3, 1]
步骤 1: 确定范围
找到最小值和最大值 最小值 1最大值 8
步骤 2: 计数 创建一个计数数组 count大小为 最大值 - 最小值 1 count 数组大小为 8从 1 到 8。初始化 count 数组为全零count [0, 0, 0, 0, 0, 0, 0, 0]。 统计每个元素出现的次数 4 → count[4 - 1] 1count [0, 0, 0, 1, 0, 0, 0, 0]2 → count[2 - 1] 1count [0, 1, 0, 1, 0, 0, 0, 0]2 → count[2 - 1] 1count [0, 2, 0, 1, 0, 0, 0, 0]8 → count[8 - 1] 1count [0, 2, 0, 1, 0, 0, 0, 1]3 → count[3 - 1] 1count [0, 2, 1, 1, 0, 0, 0, 1]3 → count[3 - 1] 1count [0, 2, 2, 1, 0, 0, 0, 1]1 → count[1 - 1] 1count [1, 2, 2, 1, 0, 0, 0, 1]
步骤 3: 累积 将 count 数组进行累积 count [1, 3, 5, 6, 6, 6, 6, 7] 累积过程 count[1] count[0]count [1, 3, 2, 1, 0, 0, 0, 1]count[2] count[1]count [1, 3, 5, 1, 0, 0, 0, 1]count[3] count[2]count [1, 3, 5, 6, 0, 0, 0, 1]count[4] count[3]count [1, 3, 5, 6, 6, 0, 0, 1]count[5] count[4]count [1, 3, 5, 6, 6, 6, 0, 1]count[6] count[5]count [1, 3, 5, 6, 6, 6, 6, 1]count[7] count[6]count [1, 3, 5, 6, 6, 6, 6, 7]
步骤 4: 排序 创建一个输出数组 output用于存放排序后的结果 output [0, 0, 0, 0, 0, 0, 0, 0] 从原数组中取出元素并根据 count 数组确定其位置 4 → output[count[4 - 1] - 1] 4count[4 - 1] - 1output [0, 0, 0, 4, 0, 0, 0, 0]2 → output[count[2 - 1] - 1] 2count[2 - 1] - 1output [0, 0, 2, 4, 0, 0, 0, 0]2 → output[count[2 - 1] - 1] 2count[2 - 1] - 1output [0, 2, 2, 4, 0, 0, 0, 0]8 → output[count[8 - 1] - 1] 8count[8 - 1] - 1output [0, 2, 2, 4, 0, 0, 0, 8]3 → output[count[3 - 1] - 1] 3count[3 - 1] - 1output [0, 2, 2, 3, 0, 0, 0, 8]3 → output[count[3 - 1] - 1] 3count[3 - 1] - 1output [0, 2, 2, 3, 3, 0, 0, 8]1 → output[count[1 - 1] - 1] 1count[1 - 1] - 1output [1, 2, 2, 3, 3, 0, 0, 8]最终 output 数组为[1, 2, 2, 3, 3, 4, 8]
算法复杂度 时间复杂度: 最坏情况: O(n k)平均情况: O(n k)最佳情况: O(n k)其中n 是元素的数量k 是元素的范围最大值 - 最小值 1。 空间复杂度: O(n k) 需要额外的空间来存储计数数组和输出数组。
优点
稳定排序计数排序是一种稳定的排序算法即相同元素的相对顺序不会改变。时间复杂度低在元素范围有限的情况下时间复杂度接近线性。
缺点
空间复杂度高需要额外的空间来存储计数数组特别是当元素的范围很大时。不适用大范围数据当数据范围远大于元素数量时计数排序的空间复杂度可能变得不可接受。
Java代码解读
public class CountingSort {// 主方法执行计数排序public static void countingSort(int[] arr) {if (arr.length 0) return;// 1. 找到最小值和最大值int min arr[0];int max arr[0];for (int num : arr) {if (num min) min num;if (num max) max num;}// 2. 创建计数数组int range max - min 1;int[] count new int[range];int[] output new int[arr.length];// 3. 计数每个元素的出现次数for (int num : arr) {count[num - min];}// 4. 累积计数数组for (int i 1; i range; i) {count[i] count[i - 1];}// 5. 排序元素到输出数组for (int i arr.length - 1; i 0; i--) {output[count[arr[i] - min] - 1] arr[i];count[arr[i] - min]--;}// 6. 将排序结果复制回原数组System.arraycopy(output, 0, arr, 0, arr.length);}public static void main(String[] args) {int[] arr {4, 2, 2, 8, 3, 3, 1};System.out.println(排序前的数组:);for (int num : arr) {System.out.print(num );}System.out.println();countingSort(arr);System.out.println(排序后的数组:);for (int num : arr) {System.out.print(num );}}
}代码说明 countingSort方法: countingSort 方法首先找到数组的最小值和最大值然后创建计数数组和输出数组。统计每个元素的出现次数并将计数数组进行累积。根据累积的计数信息将元素放到正确的位置并将排序结果复制回原数组。 找最小值和最大值: 确定数据的范围以便创建适当大小的计数数组。 计数每个元素: 使用计数数组统计每个元素的出现次数。 累积计数数组: 将计数数组累积以确定每个元素的最终位置。 排序到输出数组: 根据累积计数信息将元素放到正确的位置并将排序结果复制回原数组。
