Python算法学习之计数排序实例

计数排序是一种非比较排序算法，它的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是元素的取值范围。计数排序的基本思想是对于给定的输入序列中的每元素x，确定该序列中值小于x的元素的个数，然后将x直接存放到相应的输出序列的位置。计数排序的核心在于将输入的数据值转化为键存储在额外开的数组空间中。作为一种线性时间杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序的实现

下面是计数排序的Python实现代码：

def counting_sort(arr):
    # 获取数组的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)

    # 计算桶的数量
    bucket_num = max_val - min_val + 1

    # 初始化桶
    bucket = [0] * bucket_num

    # 计算每个元素在桶中的个数
    for i in arr:
        bucket[i - min_val] += 1

    # 计算每个元素在输出序列中的位置
    for i in range(1, bucket_num):
        bucket[i] += bucket[i - 1]

    #序列
    output = [0] * len(arr)
    for i in arr:
        output[bucket[i - min_val] - 1] = i
        bucket[i - min_val] -= 1

    return output

在这个示例中，我们首先获取输入数组的最大值和最小值，然后计算桶的数量。接着，我们初始化桶，并计算每个元素在桶中的个数。然后，我们计算每个元素在输出序列中的位置，并输出序列。最后，我们返回输出序列。

计数的示例说明

示例1

假设我们需要对以下数组进行排序：

arr = [5, 3, 2, 8, 6, 4, 1, 3]

我们可以使用以下代码对这个数组进行计数排序：

sorted_arr = counting_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3,3, 4, 5, 6, 8]

在这个示例中，我们使用计数排序对一个随机数组进行排序。计数排序的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是元素的取值范围。由于这个数组的取值范围较小，因此计数排序的时间复杂度为O(n)。

示例2

假设我们需要对以下数组进行排序：

arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

我们可以使用以下代码对这个数组进行计数排序：

sorted_arr = counting_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

在这个示例中，我们使用计数排序对一个逆序数组进行排序。计数排序的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是元素的取值范围。由于这个数组的取值范围较小，因此计数排序的时间复杂度为O(n)。

总结

计数排序是一种非常高效的排序算法，特别适用于取值范围较小的整数数组。它的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是元素的取值范围。计数排序的实现非常简单，只需要使用一个桶来存储每个元素在输入序列中出现的次数，然后再根据桶中元素的顺序输出排序结果即可。