博客

计数排序是一种线性时间复杂度的排序算法，它的时间复杂度是$O(n)$。计数排序的思想很简单，就是将每个元素出现的次数记录下来，然后再根据计数结果来确定元素的位置。

算法原理

假设我们要排序的数组为$A$，数组长度为$n$，且数组中的元素均大于等于$0$。则我们首先要找到数组中最大的元素$max$。我们可以使用循环遍历整个数组的方式来找到它：

max = A[0]
for i in range(1, n):
    if A[i] > max:
        max = A[i]

然后，我们需要一个大小为$max+1$的辅助数组$C$。$C$数组的下标表示$A$数组中的元素值，$C[i]$表示$A$数组中值等于$i$的元素的个数。

接下来，我们需要遍历一遍整个数组$A$，将每个元素的个数记录到$C$数组中。具体地，对于数组$A$中的每个元素$A[i]$，我们可以执行如下代码：

C[A[i]] += 1

最后，再遍历一遍辅助数组$C$，根据$C$数组中的计数结果将排序好的元素重新放回数组$A$中。具体地，对于数组$C$中的第$i$个元素$C[i]$，我们可以执行如下代码：

for j in range(C[i]):
    A[k] = i
    k += 1

使用方法

使用计数排序算法排序数组$A$的方法如下：

def count_sort(A):
    n = len(A)
    max = A[0]
    for i in range(1, n):
        if A[i] > max:
            max = A[i]

    C = [0] * (max + 1)
    for i in range(n):
        C[A[i]] += 1

    k = 0
    for i in range(max + 1):
        for j in range(C[i]):
            A[k] = i
            k += 1

其中，$A$是要排序的数组。

示例说明

示例一

我们来看一个简单的示例。

假设我们有一个数组$A=[3, 1, 4, 1, 5, 9, 2, 6, 5, 3]$，我们需要对它进行排序。首先，我们需要找到数组中最大的元素。很容易可以发现，$9$是数组中的最大元素。

然后，我们创建一个大小为$10$的辅助数组$C$。然后，我们遍历一遍数组$A$，将每个元素的个数记录到$C$数组中。记录完之后，$C$数组的值为：

最后，我们根据$C$数组中的计数结果将排序好的元素重新放回数组$A$中。排好序之后，$A$数组变成了$[1, 1, 2, 3, 3, 4, 5, 5, 6, 9]$。

示例二

我们再来看一个稍微复杂一些的示例。

假设我们有一个数组$A=[78, 32, 21, 85, 96, 95, 3, 12, 53, 62]$，我们需要对它进行排序。

首先，我们需要找到数组中最大的元素。很容易可以发现，$96$是数组中的最大元素。

然后，我们创建一个大小为$97$的辅助数组$C$。然后，我们遍历一遍数组$A$，将每个元素的个数记录到$C$数组中。记录完之后，$C$数组的值为：

 0  0  0  1  0  0  0  0  1  0  1  0  0  0  0  0  0  0  0  0  1  1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  1  0  0  1  0

最后，我们根据$C$数组中的计数结果将排序好的元素重新放回数组$A$中。排好序之后，$A$数组变成了$[3, 12, 21, 32, 53, 62, 78, 85, 95, 96]$。