计数排序介绍和java代码实现

计数排序介绍和Java代码实现 计数排序是一种非比较的线性时间复杂度排序算法，它通过统计每个元素在待排序数组中出现的次数，然后根据统计信息将元素放回原数组中，从而实现排序。下面是计数排序的详细介绍。 计数排序算法步骤 1. 找出待排序数组中的最大值 max 和最小值 min。 2. 创建一个计数数组 count，长度为 max-min+1，并将所有元素初始化为 0。 3. 遍历待排序数组，统计每个元素出现的次数，将计数结果存储在 count 数组中。 4. 对 count 数组进行累加操作，使得 count[i] 表示小于等于元素 i 的元素个数。 5. 创建一个与待排序数组大小相同的临时数组 result。 6. 从后往前遍历待排序数组，根据 count 数组中的累加结果，将元素放入 result 数组中的正确位置。 7. 将 result 数组复制回原数组，排序完成。 计数排序特点 1. 计数排序是稳定的排序算法，相同元素的相对顺序不会改变。 2. 算法的时间复杂度为 O(n+k)，其中 n 为待排序数组的大小，k 为计数数组的大小。 3. 计数排序适用于待排序数组中元素范围较小且分布均匀的情况。 计数排序优点 1. 计数排序是线性时间复杂度的排序算法，相对于比较排序算法具有较快的排序速度。 2. 算法的实现相对简单，不需要进行元素之间的比较。 计数排序缺点 1. 计数排序的空间复杂度较高，需要额外的计数数组来存储统计信息。 2. 当待排序数组的元素范围较大时，计数数组的大小也会相应增大，导致算法的空间占用过大。 计数排序适用场景 1. 待排序数组中元素范围较小且分布均匀的情况下，计数排序是一个较好的选择。 2. 当需要排序的元素是整数或者可以映射为整数时，计数排序也是一个可行的算法。 Java代码实现 ```java import java.util.Arrays; public class CountingSort { public static void countingSort(int[] arr) { int max = getMaxValue(arr); int min = getMinValue(arr); int range = max - min + 1; int[] count = new int[range]; int[] result = new int[arr.length]; for (int i = 0; i < arr.length; i++) { count[arr[i] - min]++; } for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } for (int i = arr.length - 1; i >= 0; i--) { result[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } System.arraycopy(result, 0, arr, 0, arr.length); } private static int getMaxValue(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } private static int getMinValue(int[] arr) { int min = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] < min) { min = arr[i]; } } return min; } public static void main(String[] args) { int[] arr = {5, 2, 9, 1, 5, 6, 3}; countingSort(arr); System.out.println(Arrays.toString(arr)); } } ``` 在上面的代码中，我们首先找到待排序数组中的最大值和最小值，然后创建一个计数数组来存储每个元素出现的次数。接着，我们遍历待排序数组，统计每个元素出现的次数，并将计数结果存储在 count 数组中。然后，我们对 count 数组进行累加操作，使得 count[i] 表示小于等于元素 i 的元素个数。我们从后往前遍历待排序数组，根据 count 数组中的累加结果，将元素放入 result 数组中的正确位置，并将 result 数组复制回原数组，排序完成。