计数排序（Counting Sort）是一种非比较排序算法，其时间复杂度为 O(n + k)，适用于范围较小的整数排序。它通过计算每个元素在数组中出现的次数来确定每个元素的位置，从而实现排序。
public class CountingSort { // 计数排序主方法 public static void countingSort(int[] arr) { if (arr == null || arr.length == 0) { return; } // 找出数组中的最大值和最小值 int max = arr[0]; int min = arr[0]; for (int num : arr) { if (num > max) { max = num; } if (num < min) { min = num; } } // 创建计数数组 int range = max - min + 1; int[] count = new int[range]; // 计算每个元素出现的次数 for (int num : arr) { count[num - min]++; } // 累加计数数组中的值 for (int i = 1; i < count.length; i++) { count[i] += count[i - 1]; } // 创建输出数组 int[] output = new int[arr.length]; // 将元素放入正确的位置 for (int i = arr.length - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } // 将排序后的数组复制回原数组 System.arraycopy(output, 0, arr, 0, arr.length); } // 打印数组 public static void printArray(int[] arr) { for (int num : arr) { System.out.print(num + " "); } System.out.println(); } // 主方法 public static void main(String[] args) { int[] arr1 = {4, 2, 2, 8, 3, 3, 1}; int[] arr2 = {9, 4, 10, 8, 2, 4, 7, 3, 6}; System.out.println("Before Sorting:"); printArray(arr1); countingSort(arr1); System.out.println("After Sorting:"); printArray(arr1); System.out.println("Before Sorting:"); printArray(arr2); countingSort(arr2); System.out.println("After Sorting:"); printArray(arr2); } }
示例1：简单整数数组排序
假设有一个简单的整数数组 [4, 2, 2, 8, 3, 3, 1]，我们可以使用计数排序对其进行排序。
public class CountingSortExample1 { public static void main(String[] args) { int[] arr = {4, 2, 2, 8, 3, 3, 1}; System.out.println("Before Sorting:"); CountingSort.printArray(arr); CountingSort.countingSort(arr); System.out.println("After Sorting:"); CountingSort.printArray(arr); } }
结果输出：
Before Sorting: 4 2 2 8 3 3 1 After Sorting: 1 2 2 3 3 4 8
示例2：包含负数的数组排序
计数排序也可以处理包含负数的数组。假设有一个数组 [9, 4, 10, 8, 2, 4, 7, 3, 6]，我们可以使用计数排序对其进行排序。
public class CountingSortExample2 { public static void main(String[] args) { int[] arr = {9, 4, 10, 8, 2, 4, 7, 3, 6}; System.out.println("Before Sorting:"); CountingSort.printArray(arr); CountingSort.countingSort(arr); System.out.println("After Sorting:"); CountingSort.printArray(arr); } }
结果输出：
Before Sorting: 9 4 10 8 2 4 7 3 6 After Sorting: 2 3 4 4 6 7 8 9 10
代码详细解释
初始化部分：
max 和 min 用于记录数组中的最大值和最小值。
range 计算出数组中元素的取值范围（即最大值与最小值之差加 1）。
count 数组用于记录每个元素出现的次数。
统计元素出现次数：
遍历输入数组，对于每个元素，计算其在 count 数组中的对应位置，并将该位置的值加 1。
累加计数：
遍历 count 数组，对于每个元素，将其值加上前一个元素的值。这样，count 数组的每个元素都包含了其前面所有元素的总和。
排序：
从输入数组的最后一个元素开始，找到其在 count 数组中的位置，并将其放到 output 数组的正确位置。
更新 count 数组，使其对应位置的值减 1。
复制回原数组：
将排序后的 output 数组复制回原始数组。
