Python实现计数排序算法

2023-04-16 00:00:00 算法 排序 计数

计数排序是一种非比较排序算法，它通过统计元素出现次数来排序。计数排序适用于元素范围不大的数组排序，时间复杂度为O(n+k)，其中n是待排序元素个数，k是元素范围。

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

def counting_sort(arr):
    max_val = max(arr)
    counts = [0] * (max_val + 1)
    for x in arr:
        counts[x] += 1
    res = []
    for i in range(len(counts)):
        res.extend([i] * counts[i])
    return res

该代码首先计算出数组中最大元素的值，然后创建一个长度为最大元素加1的counts数组，将每个元素出现次数记录下来。接着，遍历counts数组，将每个元素按照出现次数添加到结果数组中，最终返回结果数组。

相关文章