資料結構(python) —— 【18排序: 桶排序】

桶排序

上一博文講了計數排序，那麼在計數排序中，如果元素的範圍比較大(比如在1到1億之間)，如何改造算法？

桶排序(Bucket Sort): 首先将元素分在不同的桶中，再對每個桶中的元素排序

桶排序的表現取決于資料的分布，也就是需要對不同的資料排序時采取不同的分桶政策

平均情況複雜度: O(n+k)

最壞情況時間複雜度: O(k * n^2)

空間複雜度: O(nk)

桶排序原理很簡單，比如一個清單中元素最大值是max=100000，按照計數排序，我們需要一個100000大小的清單，但是如果使用桶排序，則我們可以将0-1000放一個桶裡，然後這個桶内每次放入一個元素就進行一次冒泡排序即将桶内也排好序；将1001-2000也放一個桶…這樣最大值為100000的清單隻需要放入100個桶中就行了。

代碼:

'''
TOP: 桶排序
author: Blue
time: 2020-08-08
QQ: 2458682080
'''

def bucket_sort(li, n=100, max_num=10000):
    buckets = [[] for _ in range(n)]  # 建立桶——建立n個空一維清單的二維清單
    for var in li:
        i = min(var // (max_num // n), n - 1)   # i表示var這個數放到幾号桶裡
        # max_num // n 表示每個桶有幾個數
        # 用min是為了防止比如10000這個數出現，按道理應該放到第100個桶，但我們隻有0-99号桶，是以取較小值，讓10000放進99号桶
        buckets[i].append(var)  # 把var放進桶裡
        for j in range(len(buckets[i])-1, 0, -1):  # 放入桶後，用該桶最後一個數往前進行冒泡排序
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break
    sorted_li = []
    for buc in buckets:
        sorted_li.extend(buc)
    return sorted_li

import random
li = [random.randint(0, 10000) for i in range(10000)]
li = bucket_sort(li)
print(li)
           

結果為: