Count Sort in Java: 全面解析与实践

简介

计数排序（Count Sort）是一种非比较型的排序算法，其核心思想是通过统计待排序数组中每个元素的出现次数，然后根据统计结果将元素按顺序放回原数组，从而实现排序。计数排序的时间复杂度为 $O(n + k)$，其中 $n$ 是待排序数组的长度，$k$ 是待排序数组中的最大值。由于其不基于比较操作，因此在特定场景下，计数排序的效率会高于基于比较的排序算法，如快速排序、归并排序等。本文将详细介绍计数排序在 Java 中的实现、使用方法、常见实践以及最佳实践。

基础概念

原理

计数排序的基本原理是利用数组下标来表示待排序数组中的元素，通过统计每个元素出现的次数，再根据统计结果将元素按顺序放回原数组。具体步骤如下： 1. 找出待排序数组中的最大值 $max$ 和最小值 $min$：确定计数数组的长度。 2. 创建计数数组 $count$：长度为 $max - min + 1$，用于统计每个元素出现的次数。 3. 统计每个元素出现的次数：遍历待排序数组，将每个元素的出现次数记录在计数数组中。 4. 计算计数数组的前缀和：将计数数组中每个元素的值更新为该元素及其前面所有元素的值之和，这样可以确定每个元素在排序后的数组中的位置。 5. 将元素按顺序放回原数组：遍历待排序数组，根据计数数组中记录的位置将元素放回原数组。

复杂度分析

时间复杂度：$O(n + k)$，其中 $n$ 是待排序数组的长度，$k$ 是待排序数组中的最大值。
空间复杂度：$O(k)$，主要用于存储计数数组。

适用场景

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

使用方法

以下是一个简单的 Java 实现计数排序的代码示例：

import java.util.Arrays;

public class CountSort {
    public static void countSort(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[] count = new int[max - min + 1];
        // 统计每个元素出现的次数
        for (int num : arr) {
            count[num - min]++;
        }
        // 计算计数数组的前缀和
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        // 创建临时数组
        int[] temp = new int[arr.length];
        // 将元素按顺序放回原数组
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int index = count[num - min] - 1;
            temp[index] = num;
            count[num - min]--;
        }
        // 将临时数组中的元素复制回原数组
        System.arraycopy(temp, 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));
        countSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

代码解释

找出最大值和最小值：通过遍历待排序数组，找出最大值和最小值，用于确定计数数组的长度。
创建计数数组：根据最大值和最小值创建计数数组，用于统计每个元素出现的次数。
统计每个元素出现的次数：遍历待排序数组，将每个元素的出现次数记录在计数数组中。
计算计数数组的前缀和：将计数数组中每个元素的值更新为该元素及其前面所有元素的值之和，这样可以确定每个元素在排序后的数组中的位置。
创建临时数组：用于存储排序后的元素。
将元素按顺序放回原数组：遍历待排序数组，根据计数数组中记录的位置将元素放回临时数组。
将临时数组中的元素复制回原数组：将临时数组中的元素复制回原数组，完成排序。

常见实践

处理负数

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

import java.util.Arrays;

public class CountSortWithNegative {
    public static void countSort(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 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[] temp = new int[arr.length];
        // 将元素按顺序放回原数组
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int index = count[num + offset] - 1;
            temp[index] = num;
            count[num + offset]--;
        }
        // 将临时数组中的元素复制回原数组
        System.arraycopy(temp, 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));
        countSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

稳定性排序

计数排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。在上述代码示例中，通过从后往前遍历待排序数组，可以保证相等元素的相对顺序不变。

最佳实践

优化空间复杂度

如果待排序数组中的元素取值范围较大，但实际出现的元素较少，可以使用哈希表来代替计数数组，以减少空间复杂度。以下是一个使用哈希表实现计数排序的代码示例：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CountSortWithHashMap {
    public static void countSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 创建哈希表
        Map<Integer, Integer> countMap = new HashMap<>();
        // 统计每个元素出现的次数
        for (int num : arr) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        // 找出最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : countMap.keySet()) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        // 创建临时数组
        int[] temp = new int[arr.length];
        int index = 0;
        // 将元素按顺序放回原数组
        for (int num = min; num <= max; num++) {
            if (countMap.containsKey(num)) {
                int count = countMap.get(num);
                for (int i = 0; i < count; i++) {
                    temp[index++] = num;
                }
            }
        }
        // 将临时数组中的元素复制回原数组
        System.arraycopy(temp, 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));
        countSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

小结

计数排序是一种非比较型的排序算法，具有时间复杂度为 $O(n + k)$ 的优势，适用于待排序数组中的元素取值范围较小且为整数的场景。在实际应用中，可以根据待排序数组的特点，选择合适的实现方式，如处理负数、优化空间复杂度等。通过掌握计数排序的原理和实现方法，可以在特定场景下提高排序效率。

参考资料

《算法导论》
维基百科 - 计数排序