计数排序（Count Sort）算法详解

1. 算法简介

计数排序（Count Sort）是一种非比较排序算法，其核心思想是统计数组中每个元素出现的次数，然后根据统计结果将元素按照顺序放回原数组中。计数排序的时间复杂度为O(n+k)，其中n是数组的长度，k是数组中元素的取值范围。

2. 算法实现

下面是计数排序算法的Java实现：

public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}int[] bucket = new int[max + 1];for (int i = 0; i < arr.length; i++) {bucket[arr[i]]++;}int i = 0;for (int j = 0; j < bucket.length; j++) {while (bucket[j]-- > 0) {arr[i++] = j;}}
}

3. 算法原理解析

计数排序的实现步骤如下：

1. 找到数组中的最大值max。
2. 创建一个大小为max+1的辅助数组bucket，并将其所有元素初始化为0。
3. 遍历原始数组arr，将每个元素的值作为bucket数组的下标，并将对应位置的元素值加1，表示该元素出现的次数。
4. 遍历bucket数组，根据每个元素出现的次数，依次将元素放回原始数组arr中。
5. 完成排序后，原始数组arr中的元素就按照升序排列。

4. 算法性能分析

• 时间复杂度：计数排序的时间复杂度为O(n+k)，其中n是数组的长度，k是数组中元素的取值范围。在实际应用中，当k的大小不超过n的情况下，计数排序的时间复杂度可以近似看作O(n)。
• 空间复杂度：计数排序的空间复杂度为O(k)，其中k是数组中元素的取值范围。需要额外的辅助数组bucket来统计元素出现的次数。

5. 算法应用场景

计数排序适用于以下场景：

• 数组中的元素都是非负整数，并且取值范围相对较小。
• 对稳定性要求较高的排序场景。

6. 算法测试与验证

为了验证计数排序算法的正确性，我们编写了以下辅助函数进行测试：

• comparator：使用Java内置的排序函数对数组进行排序，作为验证计数排序的参照结果。
• generateRandomArray：生成指定长度和取值范围的随机数组。
• copyArray：复制数组，用于生成计数排序的输入数组的副本。
• isEqual：判断两个数组是否相等。
• printArray：打印数组。
  // 省略部分代码…

 public static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 150;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);countSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "排序正确!" : "排序错误!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);countSort(arr);printArray(arr);
}

7. 总结

计数排序是一种非比较排序算法，适用于元素取值范围较小且对稳定性要求较高的排序场景。本文通过对计数排序算法的原理、实现步骤和性能分析进行了详细讲解，并通过测试代码验证了算法的正确性。希望本文能够帮助读者更好地理解和运用计数排序算法。

完整代码

package class08;import java.util.Arrays;public class Code02_CountSort {public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}int[] bucket = new int[max + 1];for (int i = 0; i < arr.length; i++) {bucket[arr[i]]++;}int i = 0;for (int j = 0; j < bucket.length; j++) {while (bucket[j]-- > 0) {arr[i++] = j;}}}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 150;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);countSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);countSort(arr);printArray(arr);}
}