Java 计数排序

计数排序（Counting Sort）是一种非比较型排序算法，适用于一定范围内的整数排序。它的基本思想是通过计数输入元素中每个值出现的次数，然后计算每个值的起始位置，最终将元素放到正确的位置上。计数排序的时间复杂度为 O(n + k)，其中 n 是输入数组的长度，k 是输入元素的范围。

以下是计数排序的 Java 实现：

import java.util.Arrays;  public class CountingSort {  // 计数排序算法  public static void countingSort(int[] array) {  if (array.length == 0) {  return;  }  // 找到数组中的最大值和最小值  int max = array[0];  int min = array[0];  for (int num : array) {  if (num > max) {  max = num;  }  if (num < min) {  min = num;  }  }  // 计算范围大小  int range = max - min + 1;  // 创建计数数组并初始化  int[] countArray = new int[range];  Arrays.fill(countArray, 0);  // 统计每个元素出现的次数  for (int num : array) {  countArray[num - min]++;  }  // 计算每个元素在排序后数组中的位置  int index = 0;  for (int i = 0; i < countArray.length; i++) {  while (countArray[i] > 0) {  array[index++] = i + min;  countArray[i]--;  }  }  }  // 测试计数排序算法  public static void main(String[] args) {  int[] array = {4, 2, 2, 8, 3, 3, 1};  System.out.println("排序前: " + Arrays.toString(array));  countingSort(array);  System.out.println("排序后: " + Arrays.toString(array));  }  
}

代码说明：

1. 找到数组中的最大值和最小值：遍历数组，找到其中的最大值和最小值，以便确定计数数组的范围。

2. 创建计数数组：根据最大值和最小值计算范围大小，并创建计数数组。计数数组的长度为 max - min + 1。

3. 统计每个元素出现的次数：遍历输入数组，将每个元素减去最小值，对应到计数数组的索引位置，并增加计数。

4. 计算每个元素在排序后数组中的位置：遍历计数数组，根据每个元素的计数，将其在输入数组中的位置设置好。

5. 测试代码：在 main 方法中，创建一个测试数组，调用计数排序方法，并输出排序前后的数组。

注意事项：

• 计数排序适用于范围较小的整数排序，对于范围很大的整数，计数数组可能会占用过多内存。
• 计数排序是稳定的排序算法，即相同元素的相对位置在排序前后不会改变。

通过这种方法，你可以高效地对特定范围内的整数进行排序。