Java实现计数排序算法：深入理解与实践

排序算法在计算机科学中扮演着至关重要的角色，它能够将一组无序的数据转换为有序的数据，以便后续的查找、分析等操作更加高效。计数排序（Counting Sort）是一种非比较排序算法，它通过统计每个元素在序列中出现的次数，再根据统计结果将元素按顺序输出，从而实现排序的目的。计数排序的时间复杂度为 ( O(n + k) )，其中 ( n ) 是待排序元素的个数， ( k ) 是数据范围。相比一些基于比较的排序算法（如冒泡排序、选择排序等），计数排序在特定情况下具有更高的效率。

简介

排序算法在计算机科学中扮演着至关重要的角色，它能够将一组无序的数据转换为有序的数据，以便后续的查找、分析等操作更加高效。计数排序（Counting Sort）是一种非比较排序算法，它通过统计每个元素在序列中出现的次数，再根据统计结果将元素按顺序输出，从而实现排序的目的。计数排序的时间复杂度为 ( O(n + k) )，其中 ( n ) 是待排序元素的个数， ( k ) 是数据范围。相比一些基于比较的排序算法（如冒泡排序、选择排序等），计数排序在特定情况下具有更高的效率。

目录

  1. 基础概念
    • 什么是计数排序
    • 计数排序的原理
  2. 使用方法
    • 代码示例
    • 代码解释
  3. 常见实践
    • 对整数数组进行排序
    • 处理负数情况
  4. 最佳实践
    • 优化空间复杂度
    • 与其他排序算法结合
  5. 小结
  6. 参考资料

基础概念

什么是计数排序

计数排序是一种稳定的排序算法，它适用于数据范围相对较小且数据值为整数的情况。稳定排序意味着在排序过程中，相等元素的相对顺序不会改变。例如，对于序列 [2, 3, 2, 1]，经过稳定排序后，两个 2 的相对顺序应该保持不变。

计数排序的原理

计数排序的基本原理是统计每个元素在待排序序列中出现的次数，然后根据统计结果将元素按顺序输出。具体步骤如下：

  1. 确定数据范围：找到待排序序列中的最大值 ( max ) 和最小值 ( min )，从而确定计数数组的大小。计数数组的大小通常为 ( max - min + 1 )。
  2. 统计元素出现次数：遍历待排序序列，统计每个元素出现的次数，并将其存储在计数数组中。计数数组的下标对应元素的值减去最小值，数组的值则表示该元素出现的次数。
  3. 计算前缀和：对计数数组进行累加操作，得到每个元素的前缀和。前缀和数组中的值表示小于等于该下标的元素在排序后的数组中的位置。
  4. 输出排序结果：从后往前遍历待排序序列，根据计数数组中的值确定每个元素在排序后数组中的位置，并将其放入相应位置。

使用方法

代码示例

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--) {
            sortedArr[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // 将排序结果复制回原数组
        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("Original array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        countingSort(arr);

        System.out.println("\nSorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码解释

  1. 找到最大值和最小值：通过遍历数组找到最大值 ( max ) 和最小值 ( min )，用于确定计数数组的大小。
  2. 初始化计数数组：根据最大值和最小值计算计数数组的大小 ( range = max - min + 1 )，并初始化计数数组 count。
  3. 统计元素出现次数：遍历待排序数组，将每个元素出现的次数记录在计数数组中。例如，元素 x 出现的次数存储在 count[x - min] 中。
  4. 计算前缀和：对计数数组进行累加操作，得到每个元素的前缀和。前缀和数组中的值表示小于等于该下标的元素在排序后的数组中的位置。
  5. 输出排序结果：从后往前遍历待排序数组，根据计数数组中的值确定每个元素在排序后数组中的位置，并将其放入相应位置。这样可以保证排序的稳定性。
  6. 复制结果回原数组：将排序后的数组复制回原数组，完成排序操作。

常见实践

对整数数组进行排序

上述代码示例已经展示了如何对整数数组进行计数排序。在实际应用中，只需将待排序的整数数组传递给 countingSort 方法即可。

处理负数情况

计数排序的基本实现假设数据值为非负整数。如果数据中包含负数，可以通过以下方法进行处理：

  1. 平移数据：找到数组中的最小值 ( min )，将所有元素都加上 ( |min| )，使所有元素都变为非负整数。然后对平移后的数据进行计数排序，最后再将排序结果减去 ( |min| ) 还原。
public static void countingSortWithNegative(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }

    // 找到数组中的最小值
    int min = arr[0];
    for (int num : arr) {
        if (num < min) {
            min = num;
        }
    }

    // 平移数据，使所有元素变为非负整数
    int shift = Math.abs(min);
    for (int i = 0; i < arr.length; i++) {
        arr[i] += shift;
    }

    // 进行计数排序
    countingSort(arr);

    // 还原数据
    for (int i = 0; i < arr.length; i++) {
        arr[i] -= shift;
    }
}

最佳实践

优化空间复杂度

在上述实现中，计数数组的大小为 ( max - min + 1 )。如果数据范围很大，可能会导致计数数组占用大量内存。为了优化空间复杂度，可以采用以下方法：

  1. 分桶计数：将数据范围划分为多个桶，每个桶内的数据范围较小。对每个桶内的数据进行计数排序，然后将各个桶的排序结果合并起来。

与其他排序算法结合

在实际应用中，计数排序通常与其他排序算法结合使用。例如，当数据范围较大或数据类型不是整数时，可以先使用其他排序算法（如快速排序、归并排序等）对数据进行初步排序，然后在数据范围较小的子序列上使用计数排序进行优化。

小结

计数排序是一种高效的非比较排序算法，适用于数据范围相对较小且数据值为整数的情况。通过统计元素出现的次数并利用前缀和进行排序，计数排序能够在 ( O(n + k) ) 的时间复杂度内完成排序操作。在实际应用中，我们需要根据数据的特点和需求选择合适的排序算法，并注意处理特殊情况（如负数）和优化空间复杂度。通过不断实践和优化，我们可以更好地运用计数排序算法解决实际问题。

参考资料