配置設定排序之"基數排序"

    上一篇說了桶排序，這次說一下桶排序的擴充-基數排序。

基本概念

　　要說基數排序的話，那就必須得說一下兩個概念。“基”和“桶”

　　基：基數排序裡的“基”是什麼意思呢？基的英文是radix，直接翻譯是進制的意思，在基數排序裡，指的是數字的位，比如數字123，這裡1是百位的基，2是十位的基，3是個位的基

　　桶：桶就是上一篇桶排序中的那個桶，表示一個區間内的值。

基數排序的實作

　　那麼基數排序是如何進行排序的呢？比如，有一組數字[9, 11, 31, 27, 50]，使用基數排序的話，它先對個位數 [9,1,1,7,0]進行排序，再對十位進行排序，對個位和十位都排好序了，那整組數字就是排好序的了。

1. 以個位數為依據

   根據個位定位丢進哪個桶内

   

   周遊array，元素放入對應的桶内

   

   周遊桶，輸出元素到array

   

2. 以十位為依據

   根據十位定位應該丢進哪個桶

​ 周遊桶，輸出排好序的元素

僞代碼如下：

for 每個基:

​ 第一步：周遊要排序的集合arr，放入對應的桶bucket

​ 第二步：把桶裡的元素放回arr

程式代碼如下：

def radixSort(array):
    # 1.擷取數組内的最大值、初始化基
    maxNumber = max(array)
    radix = 1

    # 2.循環排序每個基
    sortedArray = []
    while maxNumber // radix > 0:
        # 1.初始化桶數組，桶數組裡有十個桶，每個桶是一個集合
        bucketArray = [[] for i in range(10)]

        # 2.所有元素丢進對應的桶
        for i in array:
            # 元素屬于哪個桶
            bucketIndex = i / radix % 10
            bucket = bucketArray[bucketIndex]
            bucket.append(i)

        # 3.排好radix位的有序集合，傳回給while外定義的集合來接收
        sortedArray = []
        for bucket in bucketArray:
            for i in bucket:
                sortedArray.append(i)

        # 4.下一次周遊 更高一位
        radix = radix * 10

    return sortedArray

if __name__ == '__main__':
	array = [9, 11, 31, 27, 50]
	sortedAray = radixSort(array)
	print(sortedAray)
           

　　輸出結果：

[9, 11, 27, 31, 50]

Process finished with exit code 0
           

複雜度

時間複雜度 ：O(10 + r * (10 + n + n) )，其中，r是radix，如果最大數是1000，那n就是4

　　前面的10影響很小，可以去掉，複雜度O(r * (10 + n + n) )

　　r * (10 + n + n)内的10，在n很大的時候，也可以直接忽略，複雜度O(r * (n + n) )=O(2*rn)

　　同樣當n很大的時候，n和2*rn是一個意義的，去掉系數，時間複雜度是O(n)

是以，可以近似的認為，基數排序的時間複雜度是O(n)

空間複雜度：O(n + rd)

　　傳入的集合中元素個數為n，r是位數(桶的個數)，d是每一位的個數(桶内的元素個數)

基排的缺點

1. 基數排序不能處理負數（當然數組内全部加上一個正常數，使數組内全部是正數，基排好後，再減去這個正常數。這樣也可以的，但是，代價有點大）
2. 适合資料比較集中的場景，如果資料跨度很大，會造成取“基”的成本很高。