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) |