LeetCode 计数排序题解题目描述实现计数排序算法对一个整数数组进行排序。示例输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]解题思路方法计数排序思路计数排序的核心思想是通过统计数组中每个元素出现的次数然后根据统计结果重构排序后的数组。具体步骤找出数组中的最大值和最小值。创建一个计数数组用于统计每个元素出现的次数。遍历原数组统计每个元素出现的次数。根据计数数组重构排序后的数组。复杂度分析时间复杂度O(n k)其中 n 是数组的长度k 是数组中元素的范围最大值 - 最小值 1。空间复杂度O(k)需要额外的空间来存储计数数组。代码实现方法计数排序# 计数排序 def counting_sort(arr): if not arr: return arr # 找出数组中的最大值和最小值 min_val min(arr) max_val max(arr) # 计算计数数组的长度 count_len max_val - min_val 1 # 创建计数数组 count [0] * count_len # 统计每个元素出现的次数 for num in arr: count[num - min_val] 1 # 重构排序后的数组 sorted_arr [] for i in range(count_len): sorted_arr.extend([i min_val] * count[i]) return sorted_arr # 测试 def test_counting_sort(): arr [64, 34, 25, 12, 22, 11, 90] print(counting_sort(arr)) # 输出[11, 12, 22, 25, 34, 64, 90] arr [5, 4, 3, 2, 1] print(counting_sort(arr)) # 输出[1, 2, 3, 4, 5] arr [1, 2, 3, 4, 5] print(counting_sort(arr)) # 输出[1, 2, 3, 4, 5] if __name__ __main__: test_counting_sort()测试用例测试用例 1基本情况输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]测试用例 2逆序数组输入[5, 4, 3, 2, 1]输出[1, 2, 3, 4, 5]测试用例 3已排序数组输入[1, 2, 3, 4, 5]输出[1, 2, 3, 4, 5]总结计数排序是一种非比较排序算法它通过统计数组中每个元素出现的次数来实现排序。计数排序的时间复杂度为 O(n k)其中 k 是数组中元素的范围。计数排序的核心思想是通过统计数组中每个元素出现的次数然后根据统计结果重构排序后的数组。计数排序适用于元素范围较小的数组当元素范围较大时计数排序的空间复杂度会很高此时不适合使用计数排序。掌握计数排序的原理和实现对于理解非比较排序算法非常重要。