DSA 计数排序

计数排序

计数排序算法通过统计每个值出现的次数来对数组进行排序。

运行模拟，观察使用计数排序对 17 个从 1 到 5 的整数值进行排序的过程。

计数排序不像我们之前看过的排序算法那样比较值，并且只对非负整数有效。

此外，当可能的取值范围 \(k\) 小于值的个数 \(n\) 时，计数排序速度很快。

计数排序的条件

以下原因说明为什么计数排序被认为只适用于有限范围的非负整数值

• 整数值: 计数排序依赖于统计不同值的出现次数，因此这些值必须是整数。对于整数，每个值都对应一个索引（对于非负值），并且不同的值数量有限，因此可能的不同值数量 \(k\) 与值的个数 \(n\) 相比并不太大。
• 非负值: 计数排序通常通过创建一个计数数组来实现。当算法遍历要排序的值时，值 x 通过增加索引 x 处的计数数组值来进行计数。如果我们尝试排序负值，在排序值 -3 时就会遇到麻烦，因为索引 -3 将超出计数数组的范围。
• 有限的取值范围: 如果要排序的可能不同值的数量 \(k\) 大于要排序的值的数量 \(n\)，那么我们用于排序的计数数组将大于需要排序的原始数组，算法就会变得无效。

手动运行

在用编程语言实现计数排序算法之前，让我们手动运行一个简短的数组，以了解其原理。

步骤 1: 我们从一个未排序的数组开始。

步骤 2: 我们创建一个另一个数组来统计每个值出现的次数。该数组有 4 个元素，用来存储值 0 到 3。

步骤 3: 现在让我们开始计数。第一个元素是 2，因此我们必须增加索引 2 处的计数数组元素。

步骤 4: 统计完一个值后，我们可以将其删除，并统计下一个值，即 3。

步骤 5: 我们统计的下一个值是 0，因此我们在计数数组中增加索引 0 的值。

步骤 6: 我们继续这样做，直到所有值都被统计完。

步骤 7: 现在我们将从初始数组中重新创建元素，并且我们将按从低到高的顺序进行排序。

计数数组中的第一个元素告诉我们，我们有 1 个值为 0 的元素。因此，我们将 1 个值为 0 的元素推入数组，并将计数数组中索引 0 处的元素减少 1。

步骤 8: 从计数数组中我们可以看到，我们不需要创建任何值为 1 的元素。

步骤 9: 我们将 3 个值为 2 的元素推入数组的末尾。在我们创建这些元素的同时，我们也将计数数组中索引 2 处的元素减少。

步骤 10: 最后，我们必须在数组末尾添加 2 个值为 3 的元素。

最后！数组已排序。

运行下面的模拟以查看上述步骤的动画演示

手动运行：发生了什么？

在用编程语言实现该算法之前，我们需要更详细地了解上面发生了什么。

我们已经看到，计数排序算法分为两个步骤

1. 每个值都通过增加计数数组中正确索引的值来进行统计。统计完一个值后，将其删除。
2. 值通过使用计数数组中的计数和计数的索引来按正确的顺序重新创建。

有了这些，我们就可以开始使用 Python 实现该算法了。

计数排序实现

为了用编程语言实现计数排序算法，我们需要

1. 一个包含要排序的值的数组。
2. 一个接收整数数组的“计数排序”方法。
3. 方法内部用于保存值计数的数组。
4. 方法内部的一个循环，用于通过增加计数数组中的元素来统计和删除值。
5. 方法内部的一个循环，用于使用计数数组重新创建数组，使元素按正确的顺序出现。

还有一件事：我们需要找出数组中的最大值，以便能够创建大小正确的计数数组。例如，如果最大值为 5，那么计数数组总共必须有 6 个元素，以便能够统计所有可能的非负整数 0、1、2、3、4 和 5。

生成的代码如下所示

def countingSort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    while len(arr) > 0:
        num = arr.pop(0)
        count[num] += 1

    for i in range(len(count)):
        while count[i] > 0:
            arr.append(i)
            count[i] -= 1

    return arr

unsortedArr = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
sortedArr = countingSort(unsortedArr)
print("Sorted array:", sortedArr)

计数排序的时间复杂度

有关时间复杂度的一般解释，请访问 此页面。

有关插入排序时间复杂度的更全面、更详细的解释，请访问 此页面。

计数排序算法的运行速度取决于可能的取值范围 \(k\) 和值的个数 \(n\) 两种因素。

一般来说，计数排序的时间复杂度为 \(O(n+k)\)。

在最佳情况下，可能的不同值的数量 \(k\) 与值的个数 \(n\) 相比非常小，计数排序的时间复杂度为 \(O(n)\)。

但在最坏情况下，可能的不同值的数量 \(k\) 与值的个数 \(n\) 相比非常大，计数排序的时间复杂度可能为 \(O(n^2)\) 或更糟。

下面的图表显示了计数排序的时间复杂度的变化范围。

如您所见，在选择计数排序算法之前，需要考虑值的范围与要排序的值的数量之间的关系。此外，如页面顶部所述，请记住计数排序仅适用于非负整数。

运行计数排序的不同模拟，以查看操作数量如何在最坏情况\(O(n^2)\)（红线）和最佳情况\(O(n)\)（绿线）之间变化。

如前所述：如果要排序的数字的值差异很大（\(k\) 大），并且要排序的数字很少（\(n\) 小），则计数排序算法并不有效。

如果我们保持\(n\) 和\(k\) 固定，则上述模拟中的“随机”、“降序”和“升序”选项将产生相同数量的操作。 这是因为所有三种情况下都发生了相同的事情：设置计数数组，对数字进行计数，并创建新的排序数组。

[,,,4,2,1]