九大排序算法之桶排序

桶排序（Bucket Sort）

       桶排序 (Bucket sort)或所謂的箱排序，是一個排序算法， 是将一個資料表分割成許多buckets，然後每個bucket各自排序，或用不同的排序算法，或者遞歸的使用bucket sort算法。也是典型的divide-and-conquer分而治之的政策。它是一個分布式的排序，介于MSD基數排序和LSD基數排序之間。

原理：

      将數組分到有限數量的桶子裡。每個桶子再個别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排序）。

算法較長的描述：

• 設定一個定量的數組當作空桶；
• 周遊輸入資料，并且把資料一個一個放到對應的桶裡去；
• 對每個不是空的桶進行排序；
• 從不是空的桶裡把排好序的資料拼接起來。 

動圖示範：

代碼實作：

def bucketSort(arr):
    buckets = [0] * ((max(arr) - min(arr)) + 1)
    for i in range(len(arr)):
        buckets[arr[i] - min[arr]] += 1
    res = []
    for i in range(len(buckets)):
        if buckets[i] != 0:
            res += [i + min(arr)] * buckets[i]
    return res
           

時間複雜度、空間複雜度及穩定性：

       桶排序的平均時間複雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對于同樣的N，桶數量M越大，其效率越高，最好的時間複雜度達到O(N)。當然桶排序的空間複雜度為O(N+M)，如果輸入資料非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。 [1]