def bucket_sort(nums: List[int]) -> None:
"""桶排序"""
def insertion_sort(nums: List[int]) -> None:
for i in range(1, len(nums)):
t = nums[i]
j = i - 1
while j >= 0 and nums[j] > t:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = t
min_val, max_val = min(nums), max(nums)
bucket_size = max(1, (max_val - min_val) // (len(nums) - 1))
bucket_num = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_num)]
for x in nums:
buckets[(x - min_val) // bucket_size].append(x)
nums.clear()
for i in range(bucket_num):
insertion_sort(buckets[i])
nums.extend(buckets[i])