【十大排序算法】计数排序

数字在轻舞纷飞中，依次排列，如星辰般闪耀。

文章目录

• 一、计数排序
• 二、发展历史
• 三、处理流程
• 四、算法实现
• 五、算法特性
• 六、小结
• 推荐阅读

一、计数排序

计数排序是一种非比较型的排序算法，它根据待排序元素的值来确定每个元素之前的有序位置。它的基本思想是统计待排序元素中每个元素出现的次数，然后根据这些统计信息，将元素放到正确的位置上。
具体来说，计数排序的步骤如下：

1. 统计待排序数组中每个元素出现的次数，得到一个计数数组（count array）。
2. 根据计数数组中的信息，确定每个元素在排序后的数组中的位置。
3. 将待排序数组中的元素按照它们在计数数组中的位置依次放入到一个新的数组中，得到排好序的数组。

二、发展历史

计数排序是一种比较简单但非常有效的排序算法，其发展历史可以追溯到 20 世纪 50 年代。以下是计数排序的主要发展历史：

1. 早期思想： 计数排序的思想可以追溯到早期的计算机科学研究。人们意识到，在某些情况下，可以通过统计每个元素的出现次数来对元素进行排序，而不是依赖比较操作。
2. 基本概念确立： 计数排序的基本概念在 20 世纪 50 年代开始确立。在这个阶段，人们开始研究如何使用计数来排序元素，并且提出了一些基本的算法思想。
3. 正式提出： 计数排序的正式提出可以追溯到 1964 年，由美国计算机科学家 Harold H. Seward 在他的论文 “Computer Algorithms for Sorting Files” 中首次提出。Seward 描述了计数排序的基本思想和算法步骤，并探讨了其在实际应用中的潜力。
4. 进一步改进： 随着时间的推移，人们对计数排序进行了进一步的改进和优化。特别是在计算机科学领域的发展和算法研究中，出现了许多优化版本和变种，以提高计数排序的性能和适用性。
5. 实际应用： 计数排序在实际应用中得到了广泛的应用。尤其是在一些特定的情况下，例如对一定范围内的整数进行排序时，计数排序具有很高的效率，并且在某些情况下甚至可以超过其他常见的排序算法，如快速排序和归并排序。

三、处理流程

场景假设：我们需要将下面的无序数组 A 使用计数排序按从小到大进行排序。

计数排序的流程如下：

1. 找出待排序的数组中最大和最小的元素：在这个例子中，最小的元素是 1，最大的元素是 5。
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项：所以，我们得到 C = [0, 1, 1, 2, 2, 3]。这表示 1 出现了 1 次，2 出现了 1 次，3 出现了 2 次，4 出现了 2 次，5 出现了 3 次。
3. 对所有的计数累加：我们更新 C 为 C = [0, 1, 2, 4, 6, 9]。这表示小于等于 1 的元素有 1 个，小于等于 2 的元素有 2 个，小于等于 3 的元素有 4 个，小于等于 4 的元素有 6 个，小于等于 5 的元素有 9 个。
4. 反向填充目标数组：我们创建一个新的数组 B，大小和 A 相同。然后，我们遍历 A，对于 A 中的每个元素 i，我们都可以在 C 中找到小于等于 i 的元素数量，这就是 i 在 B 中的位置。然后，我们将 C[i] 减 1。

四、算法实现

public class CountingSort {
    void sort(int arr[]) {
        int n = arr.length;

        // 找出数组中的最大元素
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // 初始化计数数组，长度为最大元素加1
        int[] count = new int[max + 1];

        // 遍历原数组，统计每个元素的频率
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }

        // 对计数数组进行累加，使得 count[i] 表示小于等于 i 的元素数量
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }

        // 创建一个新的数组，用于存放排序后的结果
        int[] output = new int[n];
        // 反向遍历原数组，根据计数数组中的信息，确定每个元素在排序后数组中的位置
        for (int i = n - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;  // 每放置一个元素，相应的计数就减1
        }

        // 将排序后的结果复制回原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String args[]) {
        CountingSort cs = new CountingSort();
        int arr[] = {5, 4, 3, 2, 1, 5, 4, 3, 5};
        cs.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

算法时间复杂度分析：

五、算法特性

计数排序（Counting Sort）是一种非比较排序算法，其特性包括：

1. 稳定性： 计数排序是一种稳定的排序算法。稳定性是指对于具有相同排序键值的元素，排序前后它们的相对位置保持不变。计数排序在统计元素出现次数并进行排序时，保持了相同元素的相对顺序不变。
2. 原地性： 计数排序并不是一个原地排序算法。
3. 适用性： 计数排序适用于一定范围内的整数排序，特别是对于取值范围不大的情况。因为它不依赖于元素间的比较，而是统计每个元素出现的次数，然后根据这些统计信息确定元素的位置。
4. 空间复杂度： 计数排序的空间复杂度较高，为 O ( n + k ) O(n + k) O(n+k)，其中 n n n 是待排序元素的个数， k k k 是待排序元素中的最大值与最小值之差加 1 1 1。因为计数排序需要额外的空间来存储元素出现的次数以及辅助数组来保存排序结果。
5. 线性时间复杂度： 计数排序的时间复杂度为 O ( n + k ) O(n + k) O(n+k)，其中 n n n 是待排序元素的个数， k k k 是待排序元素中的最大值与最小值之差加 1 1 1。这意味着计数排序的时间复杂度与待排序数据的范围大小相关，而与待排序数据的数量无关。
6. 不适用于负数和浮点数： 计数排序通常用于排序非负整数，因为它要求元素必须是非负整数，并且需要知道待排序数据的范围。对于负数和浮点数，需要进行一些额外的处理才能适应计数排序的要求。
7. 不稳定范围扩展： 在一些情况下，计数排序的稳定性可能受到范围扩展的影响。如果对于相同的键值，在不同的范围内进行计数排序，可能会导致稳定性受到破坏。

六、小结

计数排序是一种简单而高效的排序算法，尤其适用于范围有限且重复元素较多的情况。通过统计每个元素的频率并根据累计频率将元素放置到正确位置上，可以在线性时间内完成排序。然而，需要注意的是，计数排序的空间复杂度较高，因为需要额外的空间来存储频率数组。

推荐阅读

1. Spring 三级缓存
2. 深入了解 MyBatis 插件：定制化你的持久层框架
3. Zookeeper 注册中心：单机部署
4. 【JavaScript】探索 JavaScript 中的解构赋值
5. 深入理解 JavaScript 中的 Promise、async 和 await