算法學習：基數排序

1、基數排序的應用場景

把一系列單詞，按照英文字典的順序排序，如 a，alice，bob ....

基數排序不具有普適性。

2、定義

基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“筒子法”（bucket sort）或bin sort。

顧名思義，它是通過鍵值的部分資訊，將要排序的元素分配至某些“桶”中，以此達到排序的作用。

基數排序法是穩定性排序其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法。

3、舉例

輸入： ["banana","apple","orange","ape","he"]

輸出： ["ape","apple","banana","he","orange"]

4、基數排序的分類

實現方法不一樣，但是實現的結果是一樣的。分為低位優先和高位優先。

5、基數排序-低位排序-字母

1）思路

　　如果對于字母進行排序，我們的字母永遠是26個基本字母進行的組合。

　　將每個字母作為一個基準的桶，只要對應位置的字母是匹配基準字母桶的，我們將其放入對應的桶里面。

　　待排序列表：["banana","apple","orange","ape","he"]

　　前置條件：把單詞按照最長單詞的長度進行填充（不是真正的填充，而是將對應位置看做a）

2）過程說明：

　　["banana","apple","orange","ape","he"]　　max_length = 6

取第六個單詞，idx=5:

　　banana banana[5] = a

　　apple"a" apple[5] ==>index out of range，bucket_index = 0（放入“a”）的桶中

　　orange orange[5] = e

　　ape"aaa" ape[5] ==>index out of range，bucket_index = 0（放入“a”）的桶中

　　he"aaaa" he[5]==>index out of range，bucket_index = 0（放入“a”）的桶中

.......

取第三個單詞，idx=2：

　　banana banana[2] = n

　　apple"a" apple[2] = p

　　.......

step1：分26個桶，以倒數第一個字母為基準查找

　　A：banana apple ape he

　　D：

　　E：orange

　　X：

　　Y：

　　Z：

step2：從A-Z依次取值放在一起，按順序取出桶里面的數組合：banana apple ape he orange

step3：分26個桶，按照倒數第二個字母為基準放置

　　A：ape he

　　D：

　　E：apple

　　G：orange

　　...

　　N：banana

　　X：

　　Y：

　　Z：

step4：按順序取出桶里面輸的組合：ape he apple orange banana

step5：分26個桶，按照（倒數）第三個字母為基準放置

　　A：ape, he, banana

　　G：

　　L：apple

　　...

　　N：orange

　　X：

　　Y：

　　Z：

step6：按順序取出桶里面輸的組合：ape he banana apple orange

...

3）代碼

#基數排序:低位優先 字母
def bucketSort(arr):
    #確定分桶并桶的次數
    max_length = len(max(arr,key=len))
    print(max_length)
    #while做的重復的分桶并桶
    while max_length>=0:
        buckets = [[] for i in range(26)]
        for word in arr:
            #假定長度不夠的情況下，把單詞放到第一個桶里面去
            if max_length>=len(word):
                bucket_idx = 0
            else:
                #長度夠的情況下，取要對比的單詞word[max_length]==》獲取對應的桶的索引
                bucket_idx = ord(word[max_length].lower())-97
            buckets[bucket_idx].append(word)
        j = 0
        #并桶:從a - z 按順序并桶
        for bucket in buckets:
            for word in bucket:
                arr[j]=word
                j+=1
        print("arr=%s"%arr)
        max_length-=1
arr = ["banana","apple","orange","ape","he","application","bat","object","able"]
print(bucketSort(arr))

'''
結果：
11
arr=['banana', 'apple', 'orange', 'ape', 'he', 'application', 'bat', 'object', 'able']
arr=['banana', 'apple', 'orange', 'ape', 'he', 'bat', 'object', 'able', 'application']
arr=['banana', 'apple', 'orange', 'ape', 'he', 'bat', 'object', 'able', 'application']
arr=['banana', 'apple', 'orange', 'ape', 'he', 'bat', 'object', 'able', 'application']
arr=['banana', 'apple', 'orange', 'ape', 'he', 'bat', 'object', 'able', 'application']
arr=['banana', 'apple', 'orange', 'ape', 'he', 'bat', 'object', 'able', 'application']
arr=['banana', 'apple', 'ape', 'he', 'bat', 'able', 'application', 'orange', 'object']
arr=['ape', 'he', 'bat', 'able', 'object', 'apple', 'orange', 'application', 'banana']
arr=['ape', 'he', 'bat', 'banana', 'able', 'object', 'apple', 'application', 'orange']
arr=['he', 'orange', 'ape', 'object', 'able', 'banana', 'apple', 'application', 'bat']
arr=['banana', 'bat', 'object', 'able', 'he', 'ape', 'apple', 'application', 'orange']
arr=['able', 'ape', 'apple', 'application', 'banana', 'bat', 'he', 'object', 'orange']
None
'''

6、基數排序-高位排序-字母

1）思路

第一步：從idx=0 開始按照字母分桶

　　A:apple,ape,able====>able,ape,apple

　　B:banana

　　C

　　D

　　　　able,ape,apple,banana

第二步：對A里面的單詞進行高位優先分桶，idx+1 = 1

　　從A桶里面拿出來的：apple,ape,able

　　A：

　　B:able

　　C

　　D

　　p:apple ,ape====》ape,apple

　　　　able,ape,apple

第三步：對p:apple ,ape桶里面的進行分桶，idx+1 = 2

　　A

　　B

　　C

　　D

　　E: ape

　　P: apple

　　所有的桶只有一個單詞了，開始合桶

　　　　ape,apple

低位優先:分桶合桶

高位優先：體現了一個分治的思想的

2）代碼

#基數排序：高位排序 字母
def bucketSortMsd(arr,idx):
    max_length = len(max(arr,key=len))
    if idx>max_length:
        return arr
    buckets = [[] for i in range(26)]
    for word in arr:
        if idx>=len(word):
            bucket_idx = 0
        else:
            bucket_idx = ord(word[idx])-97
        buckets[bucket_idx].append(word)
    arr = []
    for bucket in buckets:
        if len(bucket)>1:
            arr +=bucketSortMsd(bucket,idx+1)
        else:
            arr+=bucket
    return arr
arr = ["banana","apple","ape","he"]
print(bucketSortMsd(arr,0))

'''
結果：
['ape', 'apple', 'banana', 'he']
'''

posted @ 2020-12-08 16:13 hqq的進階日記閱讀(528) 評論(0) 收藏舉報

刷新頁面返回頂部

算法學習：基數排序

公告