Counting Sort in Java: 高效排序算法详解

简介

在计算机科学领域，排序算法是基础且关键的内容。Counting Sort（计数排序）是一种非比较型的排序算法，它的时间复杂度为 $O(n + k)$，其中 $n$ 是待排序数组的元素个数，$k$ 是待排序数组中的最大元素值。相较于一些比较型排序算法（如冒泡排序、快速排序等），计数排序在特定场景下能展现出极高的效率。本文将围绕 Counting Sort 在 Java 中的实现展开，详细介绍其基础概念、使用方法、常见实践以及最佳实践。

目录

1. 基础概念
2. 使用方法
3. 常见实践
4. 最佳实践
5. 小结
6. 参考资料

基础概念

原理

计数排序的核心思想是通过统计待排序数组中每个元素出现的次数，然后根据这些统计信息将元素有序地放回原数组。具体步骤如下： 1. 找出最大值：遍历待排序数组，找出其中的最大值 $k$。 2. 统计元素出现次数：创建一个长度为 $k + 1$ 的计数数组，用于统计每个元素出现的次数。 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 = Arrays.stream(arr).max().getAsInt();

        // 创建计数数组
        int[] count = new int[max + 1];

        // 统计元素出现次数
        for (int num : arr) {
            count[num]++;
        }

        // 计算累积次数
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 创建排序后的数组
        int[] sortedArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArr[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        // 将排序后的数组复制回原数组
        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));
    }
}

代码解释

1. 找出最大值：使用 Arrays.stream(arr).max().getAsInt() 方法找出待排序数组中的最大值。
2. 统计元素出现次数：遍历待排序数组，将每个元素作为计数数组的索引，对应位置的值加 1。
3. 计算累积次数：对计数数组进行累加操作，得到每个元素在排序后数组中的最终位置。
4. 填充排序数组：从后往前遍历待排序数组，根据累积次数将元素放入排序后的数组中，并更新计数数组。
5. 复制回原数组：使用 System.arraycopy 方法将排序后的数组复制回原数组。

常见实践

处理负数

计数排序的原始实现只能处理非负整数。如果待排序数组中包含负数，可以通过将所有元素加上一个偏移量，将负数转换为非负整数，排序完成后再减去偏移量。以下是示例代码：

import java.util.Arrays;

public class CountingSortWithNegative {
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 找出最小值和最大值
        int min = Arrays.stream(arr).min().getAsInt();
        int max = Arrays.stream(arr).max().getAsInt();

        // 计算偏移量
        int offset = -min;

        // 创建计数数组
        int[] count = new int[max - min + 1];

        // 统计元素出现次数
        for (int num : arr) {
            count[num + offset]++;
        }

        // 计算累积次数
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 创建排序后的数组
        int[] sortedArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArr[count[arr[i] + offset] - 1] = arr[i];
            count[arr[i] + offset]--;
        }

        // 将排序后的数组复制回原数组
        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));
    }
}

最佳实践

适用场景

计数排序适用于以下场景： - 待排序数组中的元素范围较小。 - 待排序数组中的元素为整数。

注意事项

• 当 $k$ 非常大时，计数排序的空间复杂度会很高，可能会导致内存溢出。
• 计数排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。

小结

本文详细介绍了 Counting Sort 在 Java 中的实现，包括基础概念、使用方法、常见实践以及最佳实践。计数排序是一种高效的非比较型排序算法，适用于特定场景。在使用时，需要注意元素范围和内存使用情况。通过合理运用计数排序，可以提高排序效率。

参考资料

• 《算法导论》
• GeeksforGeeks - Counting Sort