Java算法之计数排序（Counting Sort）

简介

计数排序是一种线性时间复杂度的排序算法，它不依赖于元素之间的比较，而是通过统计数组中每个元素出现的次数，然后根据这些统计信息对元素进行排序。这种算法特别适用于整数且整数的范围不是非常大时。

算法步骤

1. 找出数组中的最大值。
2. 创建一个计数数组，长度为最大值加一。
3. 遍历原数组，对每个元素在计数数组中对应的位置加一。
4. 再次遍历计数数组，将每个非零元素按顺序累加到原数组。

//countingSort 方法接受数组和最大值作为参数，执行计数排序。
//首先创建一个计数数组，长度为最大值加一。
//遍历原数组，统计每个元素出现的次数。
//再次遍历计数数组，将非零元素累加到原数组。
//main 方法中，我们初始化一个数组，找出最大值，然后调用 countingSort 方法进行排序，并打印排序后的结果。
public class CountingSort {// 计数排序方法public static void countingSort(int[] arr, int maxVal) {int n = arr.length;int[] count = new int[maxVal + 1]; // 创建计数数组// 统计每个元素出现的次数for (int i = 0; i < n; i++) {count[arr[i]]++;}// 将计数数组中非零元素累加到原数组int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {arr[index++] = i;count[i]--;}}}public static void main(String[] args) {int[] arr = {4, 2, 2, 8, 3, 3, 1};int maxVal = getMaxVal(arr); // 找出数组中的最大值countingSort(arr, maxVal);// 打印排序后的数组for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}// 辅助方法，找出数组中的最大值private static int getMaxVal(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}return max;}
}

优点

• 时间效率：对于小范围整数排序，计数排序的时间复杂度是O(n+k)，其中n是数组长度，k是整数的范围。
• 稳定性：计数排序是稳定的排序算法，相等元素的相对位置不会改变。
• 简单性：算法逻辑简单，容易实现。

缺点

• 空间复杂度：计数排序需要额外的存储空间，其大小取决于整数的范围，空间复杂度为O(k)。
• 适用范围：只适用于整数排序，对于非整数或整数范围非常大的情况，效率不高。

时间复杂度和空间复杂度分析

• 时间复杂度：O(n+k)，其中n是数组长度，k是整数的范围。
• 空间复杂度：O(k)，需要一个大小为k的计数数组。

使用场景

• 当整数的范围k远小于数组长度n时，计数排序非常高效。
• 适用于对固定范围的整数进行排序，如统计字符出现次数。