计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1、算法步骤

计数排序是一种非比较型的排序算法，其基本思想是统计每个元素出现的次数，然后根据统计信息将元素放回到正确的位置上。

a. 确定范围：遍历待排序的数组，确定数组中的最大值maxValue。

b. 初始化桶：创建一个大小为maxValue+1的桶（也可以理解为计数数组），并将所有桶的值初始化为0。

d. 统计元素出现次数：遍历待排序的数组，将每个元素作为桶的索引，统计数组中每个元素出现的次数，存储在桶中。

d. 累加计数：对于每个桶中的计数值，累加前面的计数值，使得桶中的值表示小于等于当前索引的元素个数。

e. 排序：遍历原始数组，根据桶中的计数信息，将每个元素放回到其正确的位置上，放置完成后，将桶中对应索引的计数值减1。

f. 输出排序后的数组：所有元素都被放回到了正确的位置上，得到排序后的数组。

计数排序的关键步骤是统计元素出现的次数并将其映射到桶中，以及根据桶中的计数信息将元素放回原数组中的正确位置。这样做的时间复杂度是O(n + k)，其中n是数组的长度，k是桶的数量（最大值加1）。

2、动图演示

3、代码

# 定义一个函数countingSort，参数为一个列表arr和最大值maxValue
def countingSort(arr, maxValue):
    # 计算桶的数量，桶的数量等于最大值加1
    bucketLen = maxValue + 1
    # 初始化桶，所有桶的值均为0
    bucket = [0] * bucketLen
    # 初始化排序后的索引
    sortedIndex = 0
    # 获取数组长度
    arrLen = len(arr)
    # 遍历数组，统计每个元素出现的次数
    for i in range(arrLen):
        # 如果桶中没有当前元素的索引，则初始化为0
        if not bucket[arr[i]]:
            bucket[arr[i]] = 0
        # 将当前元素对应桶的计数加1
        bucket[arr[i]] += 1
    # 遍历桶，根据计数将元素依次放回原数组中
    for j in range(bucketLen):
        # 当桶中有元素时
        while bucket[j] > 0:
            # 将当前桶的索引值依次放回原数组中
            arr[sortedIndex] = j
            sortedIndex += 1
            # 将当前桶的计数减1
            bucket[j] -= 1
    # 返回排序后的数组
    return arr

打赏 支付宝打赏 微信打赏