排序算法之计数排序详细解读（附带Java代码解读）
计数排序（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] += 1，count = [0, 0, 0, 1, 0, 0, 0, 0] - 2 →
count[2 - 1] += 1，count = [0, 1, 0, 1, 0, 0, 0, 0] - 2 →
count[2 - 1] += 1，count = [0, 2, 0, 1, 0, 0, 0, 0] - 8 →
count[8 - 1] += 1，count = [0, 2, 0, 1, 0, 0, 0, 1] - 3 →
count[3 - 1] += 1，count = [0, 2, 1, 1, 0, 0, 0, 1] - 3 →
count[3 - 1] += 1，count = [0, 2, 2, 1, 0, 0, 0, 1] - 1 →
count[1 - 1] += 1，count = [1, 2, 2, 1, 0, 0, 0, 1]
- 4 →
步骤 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] = 4，count[4 - 1] -= 1，output = [0, 0, 0, 4, 0, 0, 0, 0] - 2 →
output[count[2 - 1] - 1] = 2，count[2 - 1] -= 1，output = [0, 0, 2, 4, 0, 0, 0, 0] - 2 →
output[count[2 - 1] - 1] = 2，count[2 - 1] -= 1，output = [0, 2, 2, 4, 0, 0, 0, 0] - 8 →
output[count[8 - 1] - 1] = 8，count[8 - 1] -= 1，output = [0, 2, 2, 4, 0, 0, 0, 8] - 3 →
output[count[3 - 1] - 1] = 3，count[3 - 1] -= 1，output = [0, 2, 2, 3, 0, 0, 0, 8] - 3 →
output[count[3 - 1] - 1] = 3，count[3 - 1] -= 1，output = [0, 2, 2, 3, 3, 0, 0, 8] - 1 →
output[count[1 - 1] - 1] = 1，count[1 - 1] -= 1，output = [1, 2, 2, 3, 3, 0, 0, 8]
最终
output数组为：[1, 2, 2, 3, 3, 4, 8] - 4 →
算法复杂度
-
时间复杂度:
- 最坏情况: 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方法首先找到数组的最小值和最大值，然后创建计数数组和输出数组。- 统计每个元素的出现次数，并将计数数组进行累积。
- 根据累积的计数信息将元素放到正确的位置，并将排序结果复制回原数组。
-
找最小值和最大值:
- 确定数据的范围，以便创建适当大小的计数数组。
-
计数每个元素:
- 使用计数数组统计每个元素的出现次数。
-
累积计数数组:
- 将计数数组累积，以确定每个元素的最终位置。
-
排序到输出数组:
- 根据累积计数信息将元素放到正确的位置，并将排序结果复制回原数组。