28 lines
945 B
Python
28 lines
945 B
Python
|
"""
|
|||
|
|
计数排序：
|
|||
|
|
|
|||
|
|
1. 遍历数组，找出其中的最大数字，记为 m，然后创建一个长度为 m+1 的辅助数组 counter 。
|
|||
|
|
2. 借助 counter 统计 nums 中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。
|
|||
|
|
3. 统计方法很简单，只需遍历 nums（设当前数字为 num），每轮将 counter[num] 增加 1 即可。
|
|||
|
|
4. 由于 counter 的各个索引天然有序，因此相当于所有数字已经排序好了。接下来，我们遍历 counter ，根据各数字出现次数从小到大的顺序填入 nums 即可。
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
def counting_sort(nums: list[int]):
|
|||
|
|
m = max(nums)
|
|||
|
|
|
|||
|
|
counter = [0] * (m + 1)
|
|||
|
|
for num in nums:
|
|||
|
|
counter[num] += 1
|
|||
|
|
|
|||
|
|
i = 0
|
|||
|
|
|
|||
|
|
for index, value in enumerate(counter):
|
|||
|
|
if value > 0:
|
|||
|
|
for j in range(value):
|
|||
|
|
nums[i] = index
|
|||
|
|
i += 1
|
|||
|
|
|
|||
|
|
nums = [54, 32, 99, 18, 75, 31, ]
|
|||
|
|
counting_sort(nums)
|
|||
|
|
print(nums)
|