Bucket Sort(桶子排序法)
學習資源
牛刀小試
- Leetcode 的 912
範例程式碼
python
def bucketSort(nums:List[int]):
max_num = max(nums)
min_num = min(nums)
size = 5
buckets = [[] for _ in range(math.floor((max_num - min_num)/size+1))]
for num in nums:
buckets[int(num-min_num)/size].append(num)
result = []
for i in range(len(buckets)):
buckets[i] = sorted(buckets[i])
# buckets[i] = insertion_sort(buckets[i])
for j in range(len(buckets[i])):
result.append(buckets[i][j])
return result裡面的排序可以用插入排序法
python
def insertion_sort(bucket: List[int]) -> List[int]:
for i in range(1, len(bucket)):
key = bucket[i]
j = i - 1
while j >= 0 and key < bucket[j]:
bucket[j + 1] = bucket[j]
j -= 1
bucket[j + 1] = key
return bucketContributors
lucashsu95