created by Dejavu

• 代碼

這里的桶排的寫法是利用創(chuàng)建一個長度為輸入數(shù)組array最大值的臨時數(shù)組book,然后把array中的值逐一代入book的索引，對應(yīng)的book數(shù)組索引下的值就是數(shù)字出現(xiàn)的次數(shù)，從而返回book中的非零索引即可

def bucket_sort(array):
    if not array:
        return False
    max_len = max(array)+1
    book = [0 for x in range(0,max_len)]
    for i in array:
        book[i] += 1
    return [i for i in range(0,max_len) for j in range(0,book[i])]

• 改進

缺陷：無法排負(fù)數(shù)，無法排小數(shù)，book所占的空間由輸入數(shù)組的最大值確定

改進：

1. 針對存在負(fù)數(shù)的情況

   # 可對負(fù)數(shù)排序
   def bucket_sort(array):
       if not array:
           return False
       offset = min(array)
       max_len = max(array) - offset + 1
       book = [0 for x in range(0,max_len)]
       for i in array:
           book[i - offset] += 1
       return [i + offset for i in range(0,max_len) for j in range(0,book[i])]
   

2. 針對存在小數(shù)的情況

   # 可對小數(shù)排序
   def bucket_sort(array):
       if not array:
           return False
       # 保留兩位小數(shù)
       accuracy = 100.
       offset = int(min(array) * accuracy)
       max_len = int(max(array) * accuracy - offset + 1)
       book = [0 for x in range(0,max_len)]
       for i in array:
           book[int(i * accuracy - offset)] += 1
       return [(i + offset) / accuracy for i in range(0,max_len) for j in range(0,book[i])]
   

3. 利用傳統(tǒng)的逐位進行桶排

   這邊想到可以在十行內(nèi)實現(xiàn)的方法實在是太不易讀了，如果你有什么清晰的實現(xiàn)代碼的話歡迎留言告知