基數排序法.

Presentation on theme: "基數排序法."— Presentation transcript:

1 基數排序法

2 不同類型的排序演算法 採取比較與交換技巧（Comparison & Swap）
利用鍵值（Key）來與欲排序的數字做比較，合乎某種條件就將Key與被比較的數字做交換的動作 相關排序演算法 插入排序法 選擇排序法 氣泡排序法 快速排序法 合併排序法 採取分配與合併技巧（Distribution & Merge） 排序過程中，透過分配與合併動作的反覆運行，達到排序的目的。 相關排序演算法：基數排序法

3 基數排序法 基數排序法（Radix Sort）屬於「分配式排序」（Distribution Sort），又稱為多鍵排序（Multi-Key Sort）或桶子演算法（Bucket Sort）。 基數排序是依據每個記錄的鍵值劃分為若干單元，把相同的單元放置在同一箱子，常用於卡片或信件的分類機。 基數排序法是屬於穩定性（stable）的排序，其時間複雜度為O（n logr m），其中r為所採取的基數，而m為堆數。在某些情況下所需時間是O（n），所需空間很大，需要（n*n），n為記錄數。

4 基數排序法的兩種運作方式 依其運作方式可分為兩種：
最低位數優先（Least Significant Digit First；LSD） 是從最右邊的位數開始，只須採用分配和合併兩個步驟。 最高位數優先（Most Significant Digit First；MSD） 是從最左邊的位數開始，採用分配、插入排序、合併等三個步驟進行。 LSD的基數排序適用於位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方式恰與LSD相反，是由高位數為基底開始進行分配，其他的演算方式則都相同。

5 最低位數優先法(LSD) 運作原理： 是從最右邊的位數開始分配 假設r為基底（Base，或稱進制），則準備r個Buckets
假設d為最大鍵值的位數個數，則須執行d回合才能完成sort工作。 以3位數的數字來排序，必須進行3回合排序 以撲克牌排序(花色+數字)，必須進行2回合排序 從最低位數到最高位數執行各個回合，每回合做： 依位數值，將資料分配到對應的Bucket中Distribution（分配） 合併r個BucketsMerge（合併） 由「左而右」合併為「遞增排序」 由「右而左」合併為「遞減排序」

6 三位數的LSD Radix Sort (1/5) Q：欲將下列數字以LSD Radix Sort加以排序（Base=10，十進制）
179, 208, 306, 93, 859, 984, 55, 9, 271, 33

7 三位數的LSD Radix Sort (2/5) 運作方式： Base=10，∴準備10個桶子，編號為0～9。
最大的數值是984，有三個位數，∴d=3，同時可知道需執行3個回合才會完成Sort工作 第一回合：從最低位數（個位數）開始執行 依（個位數），將資料分配到對應的Bucket中→Distribution（分配） 合併10個Buckets（從0～9）→ Merge（合併） 第二回合：依據中間位數（十位數）執行 依（十位數），將資料分配到對應的Bucket中→ Distribution（分配） 合併10個Buckets（從0～9） → Merge（合併） 第三回合：以最高位數（百位數）執行 依（百位數），將資料分配到對應的Bucket中→ Distribution（分配）

8 三位數的LSD Radix Sort (3/5)

9 三位數的LSD Radix Sort (4/5) 依此類推，依序將十個數字放入適當的桶子中。 再依序0-9將所有桶子中的數字合併起來
如此即完成第一回合（針對個位數）的流程

10 三位數的LSD Radix Sort (5/5) 接著以第一回合的合併結果，進行第二回合（流程與第一回合相同）。
接著以第二回合的合併結果，進行第三回合（流程與第一回合相同）。 此時，輸出的結果即為由小到大的排序結果。

11 最高位數優先法(MSD) 運作原理： 從最左邊的位數開始分配
以3位數的百位數來分配，假設r為基底（Base，或稱進制），則準備r個Buckets 其基底為10 ，必須準備0-9個Buckets 將桶子中的多個物件個別獨立使用插入法進行排序 插入排序法的詳細步驟請參考『插入排序法』之單元 合併r個BucketsMerge（合併） 由「左而右」合併為「遞增排序」 由「右而左」合併為「遞減排序」

12 三位數的MSD Radix Sort (1/5) Q：欲將下列數字以MSD Radix Sort加以排序（Base=10，十進制）
179, 208, 306, 93, 859, 984, 55, 9, 271, 33

13 三位數的MSD Radix Sort (1/5) Q：欲將下列數字以MSD Radix Sort加以排序（Base=10，十進制）
179, 208, 306, 93, 859, 984, 55, 9, 271, 33 運作原理： Step1：以百位數開始進行分配 33 9 55 271 93 179 208 306 859 984 1 2 3 4 5 6 7 8

14 三位數的MSD Radix Sort (1/5) 運作原理： Step2：將桶子中的多個物件個別獨立使用插入法進行排序
9、33、55、93、179、208、271、306、859、984 93 55 33 271 9 179 208 306 859 984 1 2 3 4 5 6 7 8