Bucket Sort

桶子排序法 (Bucket Sort) 想法很簡單，其實就是準備幾個桶子，將要排序的資料分類丟至指定的桶子中，再依序將桶子裡的東西取出。

---

假設我們現在有一筆班上的成績想要排序：

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

1.準備桶子

準備好每個分數的空桶子(0)

max_score = 100
bucket = []
for i in range(max_score+1):
    bucket.append(0)

## 2.分類成績

接著把未排序的成績們放入相對應分數的桶子 每次桶子+1

for score in data:
    bucket[score] = bucket[score] + 1

## 3.讀取成績

依序檢查每個桶子是否有東西在裡面(非0) 有的話看此桶子有幾個，一個一個拿出來排好 最後就得出排序完的分數了

index = 0
for i in range(len(bucket)):
    if bucket[i] != 0:
        for j in range(bucket[i]):
            data[index] = i
            index += 1

## 4.完整程式碼

程式時間複雜度：O(M+N)

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def bucketsort(data):
    max_score = 100
    bucket = []
    
    for i in range(max_score+1):
        bucket.append(0)
    for score in data:
        bucket[score] = bucket[score] + 1

    index = 0
    for i in range(len(bucket)):
        if bucket[i] != 0:
            for j in range(bucket[i]):
                data[index] = i
                index += 1

bucketsort(data)
print(data)

[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

練習

如果假設我們的資料還包含了姓名在內，那要如何排序呢？

data = [['Abby', 58], ['Julia', 44], ['Jane', 31], ['Stephen', 76], ['Ryn', 82], ['Justin', 99], ['Caroline', 65], ['James', 87], ['Damon', 25], ['Elena', 76]]

我的答案：

陣列

data = [['Abby', 58], ['Julia', 44], ['Jane', 31], ['Stephen', 76], ['Ryn', 82], ['Justin', 99], ['Caroline', 65], ['James', 87], ['Damon', 25], ['Elena', 76]]

max_value = 100
bucket = []
data_sorted = []

for i in range(max_value + 1):
    bucket.append([])

for i in data:
    bucket[i[1]].append(i[0])

for i, j in enumerate(bucket):
    if len(j) != 0:
        for name in j:
	        data_sorted.append([name, i])

print(data_sorted) 

[['Damon', 25], ['Jane', 31], ['Julia', 44], ['Abby', 58], ['Caroline', 65], ['Stephen', 76], ['Elena', 76], ['Ryn', 82], ['James', 87], ['Justin', 99]] 以上是利用陣列，但其實也可以用字典

字典

簡略

參考資料

桶子排序法