排序算法（七）：计数排序

复杂度时间复杂度空间复杂度最好情况O(n + k)O(n + k)最坏情况O(n + k)O(n + k)平均情况O(n + k)O(n + k)计数排序：对于元素值范围较小且分布均匀的情况，计数排序能够提供线性时间复杂度O(n+k)，表现非常高效。它是一个稳定的排序算法，但对于大范围的元素值或者包含负数的情况，使用计数排序可能会导致空间复杂度过高。快速排序与归并排序：这两种排序算法的时间复杂度在

一碗黄焖鸡三碗米饭

1101人浏览 · 2025-06-06 14:51:25

一碗黄焖鸡三碗米饭 · 2025-06-06 14:51:25 发布

计数排序深度解析：原理、Java实现与性能分析

1. 计数排序的基本原理

计数排序的步骤

2. 计数排序的时间复杂度与空间复杂度分析

计数排序（Counting Sort）是一种非比较型排序算法，其主要思想是通过统计待排序元素出现的次数来确定元素的最终位置。尽管计数排序的时间复杂度为 O(n+k)，其中 n 是待排序元素的个数，k 是元素值的范围，它在元素值范围较小的情况下，能够提供非常高效的排序表现。本文将详细讲解计数排序的原理、Java实现与性能分析，并与其他常见排序算法进行对比。

1. 计数排序的基本原理

计数排序是通过以下几个步骤完成排序的：

统计每个元素的频次：对于待排序的每个元素，统计它出现的次数。
计算累加频次：将频次转换为累加频次，使得每个元素能够知道其应该插入的位置。
放置元素到正确位置：根据累加频次，逐个将元素放置到新的排序数组中。

计数排序的步骤

假设我们有一个数组 [4, 2, 2, 8, 3, 3, 1, 9]，并且要求对其进行排序，最大元素为 9。具体过程如下：

统计频次：统计每个元素出现的次数。
- 1: 1 次
- 2: 2 次
- 3: 2 次
- 4: 1 次
- 8: 1 次
- 9: 1 次
计算累加频次：累加每个元素的频次。
- 1: 1
- 2: 3
- 3: 5
- 4: 6
- 8: 7
- 9: 8
重新排列元素：按照累加频次的顺序将元素放到正确的位置，得到排序后的数组 [1, 2, 2, 3, 3, 4, 8, 9]。

2. 计数排序的时间复杂度与空间复杂度分析

2.1 时间复杂度

计数排序的时间复杂度主要由以下三个部分组成：

统计频次：需要遍历输入数组，时间复杂度为 O(n)，其中 n 是待排序数组的大小。
计算累加频次：需要遍历频次数组，时间复杂度为 O(k)，其中 k 是元素的取值范围。
放置元素：需要遍历输入数组，并根据累加频次重新放置元素，时间复杂度为 O(n)。

因此，计数排序的总时间复杂度为 O(n+k)，其中 n 是待排序数组的大小，k 是元素值的最大值。

2.2 空间复杂度

计数排序需要额外的空间来存储频次数组和排序结果数组。频次数组的大小为 O(k)，排序结果数组的大小为 O(n)。因此，计数排序的空间复杂度为 O(n + k)。

2.3 总结

复杂度	时间复杂度	空间复杂度
最好情况	O(n + k)	O(n + k)
最坏情况	O(n + k)	O(n + k)
平均情况	O(n + k)	O(n + k)

3. 计数排序的Java实现

3.1 基本实现

以下是一个标准的计数排序实现：

public class CountingSort {

    public static void countingSort(int[] arr) {
        // 找到最大值和最小值
        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[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // 将排序后的结果拷贝回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1, 9};
        System.out.println("排序前：");
        printArray(arr);

        countingSort(arr);

        System.out.println("排序后：");
        printArray(arr);
    }
}

3.2 代码解释

countingSort：是计数排序的主方法。首先找出数组中的最小值和最大值，创建一个计数数组来统计元素出现的次数，然后计算累加频次，最后将元素放到正确的位置。
printArray：打印数组的方法。

3.3 示例输出

排序前：
4 2 2 8 3 3 1 9 
排序后：
1 2 2 3 3 4 8 9

4. 计数排序的优化

虽然计数排序在元素值范围较小的情况下表现优异，但它的缺点也很明显：

空间复杂度高：当元素值范围较大时，计数排序会占用大量空间。
不适用负数：计数排序本身无法处理负数，因为它依赖于元素值的范围进行计数。

4.1 优化方法

压缩计数数组：如果元素值范围很大，我们可以采用一些优化方法来压缩计数数组。例如，如果元素值是稀疏的，可以使用哈希表代替计数数组。
处理负数：如果元素中有负数，可以通过将数组中的所有元素加上一个常数值（使得所有元素非负）来处理负数。
限制范围：对于元素值范围非常大的数据，计数排序不再是最优选择。此时可以考虑使用其他排序算法，如归并排序、快速排序等。

5. 计数排序与其他排序算法的对比

我们将计数排序与其他常见的排序算法（如快速排序、归并排序、插入排序等）进行对比，看看它在不同场景下的表现：

排序算法	最好情况时间复杂度	最坏情况时间复杂度	平均时间复杂度	空间复杂度	稳定性
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定
快速排序	O(n log n)	O(n^2)	O(n log n)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定

5.1 总结

计数排序：对于元素值范围较小且分布均匀的情况，计数排序能够提供线性时间复杂度 O(n+k)，表现非常高效。它是一个稳定的排序算法，但对于大范围的元素值或者包含负数的情况，使用计数排序可能会导致空间复杂度过高。
快速排序与归并排序：这两种排序算法的时间复杂度在大多数情况下为 O(n log n)，适用于更广泛的场景，尤其是在元素值范围较大的情况下。
插入排序：适用于小规模数据或者几乎有序的数据，空间复杂度低，但时间复杂度较高。

6. 结语

计数排序是一种高效的非比较型排序算法，适用于元素值范围较小的场景。通过合理利用计数数组和累加频次的技巧，计数排序能够在许多实际应用中提供非常快的排序速度。尽管它有一定的局限性，但在适当的场景下，计数排序依然是一种非常实用的算法。在选择排序算法时，我们需要根据数据的特点（如元素值范围、稳定性要求等）做出合理的选择。

推荐阅读：