Java 计数排序：原理、实践与最佳实践

简介

计数排序（Counting Sort）是一种非比较排序算法，它通过统计每个元素在序列中出现的次数，进而确定每个元素在排序后序列中的位置。相较于其他排序算法，计数排序具有线性时间复杂度，适用于排序范围相对较小的整数序列。本文将详细介绍 Java 中计数排序的基础概念、使用方法、常见实践以及最佳实践。

基础概念

计数排序的核心思想是利用数组下标来表示元素的值，并统计每个元素出现的次数。具体步骤如下： 1. 找出待排序数组中的最大值和最小值：确定计数数组的范围。 2. 统计每个元素出现的次数：使用计数数组记录每个元素的出现次数。 3. 计算每个元素的累积次数：通过累加计数数组中的元素，确定每个元素在排序后数组中的位置。 4. 将元素放入排序后数组：根据累积次数将元素放入排序后数组的正确位置。

计数排序的时间复杂度为 $O(n + k)$，其中 $n$ 是待排序数组的长度，$k$ 是计数数组的范围。由于需要额外的计数数组，空间复杂度为 $O(k)$。

使用方法

以下是 Java 实现计数排序的基本代码示例：

import java.util.Arrays;

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            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 < range; i++) {
            count[i] += count[i - 1];
        }
        // 排序结果数组
        int[] sortedArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = arr[i] - min;
            sortedArr[count[index] - 1] = arr[i];
            count[index]--;
        }
        // 将排序结果复制回原数组
        System.arraycopy(sortedArr, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Before sorting: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

代码解释

找出最大值和最小值：遍历待排序数组，找出最大值和最小值，确定计数数组的范围。
统计每个元素出现的次数：使用计数数组 count 记录每个元素的出现次数。
计算累积次数：通过累加计数数组中的元素，确定每个元素在排序后数组中的位置。
将元素放入排序后数组：根据累积次数将元素放入排序后数组的正确位置。
复制排序结果：将排序结果复制回原数组。

常见实践

排序正整数数组

计数排序适用于排序范围相对较小的正整数数组。例如，对学生的考试成绩进行排序，成绩范围通常在 0 到 100 之间，可以使用计数排序高效地完成排序任务。

排序字符数组

计数排序也可以用于排序字符数组。由于字符的 ASCII 码值是整数，可以将字符数组转换为整数数组，然后使用计数排序进行排序。以下是一个示例代码：

import java.util.Arrays;

public class CountingSortForChars {
    public static void countingSort(char[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 字符的 ASCII 码范围是 0 到 127
        int range = 128;
        int[] count = new int[range];
        // 统计每个字符出现的次数
        for (char c : arr) {
            count[c]++;
        }
        // 计算累积次数
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        // 排序结果数组
        char[] sortedArr = new char[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = arr[i];
            sortedArr[count[index] - 1] = arr[i];
            count[index]--;
        }
        // 将排序结果复制回原数组
        System.arraycopy(sortedArr, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        char[] arr = {'d', 'a', 'c', 'b', 'a'};
        System.out.println("Before sorting: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

最佳实践

选择合适的排序算法

计数排序适用于排序范围相对较小的整数序列。如果排序范围过大，计数数组的空间开销会非常大，此时可以选择其他排序算法，如快速排序、归并排序等。

处理负数

如果待排序数组中包含负数，可以通过将所有元素加上一个偏移量，将负数转换为非负数，然后使用计数排序进行排序，最后再减去偏移量得到原序列的排序结果。

优化空间复杂度

在某些情况下，可以通过只记录非零计数的元素，减少计数数组的空间开销。

小结

计数排序是一种高效的非比较排序算法，具有线性时间复杂度。它适用于排序范围相对较小的整数序列，如正整数数组、字符数组等。在使用计数排序时，需要注意选择合适的排序算法，处理负数和优化空间复杂度。通过掌握计数排序的原理和实践，我们可以在特定场景下高效地完成排序任务。