Chapter 8 排序 資料結構導論 - C語言實作

8.1 前言 排序(Sort) ： 乃是將檔案中的紀錄(Records)依照特定欄位(Field)(或稱屬性(Attribute))的資料值來重新排列順序。 排序時須指定： 用哪一個欄位的資料值來排序。 按遞增(Ascending Order)或 按遞減(Descending Order)之順序來排序。 鍵(Key)：用來排序的欄位。 鍵值(Key Value)：欄位的資料值。 資料結構導論 - C語言實作

8.2 檔案、紀錄、欄位、索引與排序 檔案 資料表 欄位、屬性、資料行 紀錄、資料列 索引 資料結構導論 - C語言實作

8.2 檔案、紀錄、欄位、索引與排序 資料表(Table) 資料結構導論 - C語言實作

8.2 檔案、紀錄、欄位、索引與排序 索引(Index) 資料結構導論 - C語言實作

8.2 檔案、紀錄、欄位、索引與排序 索引(Index) 資料結構導論 - C語言實作

8.3 內部排序法(Internal Sort) 內部排序法 外部排序法 利用記憶體來排序 速度快 利用磁碟、磁帶等輔助記憶體來排序 速度慢 資料結構導論 - C語言實作

8.3 內部排序法(Internal Sort) 8.3.1. 氣泡浮昇排序法(Bubble Sort)。 8.3.2.  挑選排序法(Selection Sort)。 8.3.3.  插入排序法(Insertion Sort)。 8.3.4.  謝耳排序法(Shell Sort)。 8.3.5.  快速排序法(Quick Sort)。 8.3.6.  樹排序法 (Tree Sort)。 8.3.7.  堆積排序法(Heap Sort)。 8.3.8.  合併排序法(Merge Sort)。 8.3.9. 基數排序法(Radix Sort)。 資料結構導論 - C語言實作

8.3.1.  氣泡浮昇排序法(Bubble Sort) 採用氣泡浮昇排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序(Non-decreasing Order)加以排列的步驟如下： 步驟1：將n筆記錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號記錄的鍵值、d[1]儲存第1號記錄的鍵值、…、d[n-1]儲存第n-1號記錄的鍵值。 資料結構導論 - C語言實作

8.3.1.  氣泡浮昇排序法(Bubble Sort) 步驟2：重複執行步驟3共計n-1回合，其中若有任一回合完全沒有發生陣列元素值「交換」的情形時，就執行步驟4。 步驟3：依序比較陣列d中相鄰兩元素之鍵值；即第i回合須依序比較(d[0]和d[1])、(d[1]和d[2])、(d[2]和d[3])、...、 (d[n-i+1]和d[n-i])；若前面的元素d[x]大於後面的元素d[x+1]，則立刻將d[x]與d[x+1]之值「交換」。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-i]之值。 資料結構導論 - C語言實作

8.3.1. 氣泡浮昇排序法(Bubble Sort) 【例1】氣泡浮昇排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99} 已經儲存在一維陣列d[8]中。 按照「鍵值不遞減」的順序加以排序 資料結構導論 - C語言實作

8.3.1.  氣泡浮昇排序法(Bubble Sort) 第1回合相鄰元素兩兩比較、交換位置之分解動作 資料結構導論 - C語言實作

8.3.1.  氣泡浮昇排序法(Bubble Sort) 資料結構導論 - C語言實作

8.3.1. 氣泡浮昇排序法(Bubble Sort) 穩定排序(Stable Sort) ： 不穩定排序(Unstable Sort) 相同鍵值的資料於排序後仍然保持排序前之前後關係者 不穩定排序(Unstable Sort) 資料結構導論 - C語言實作

8.3.2. 挑選排序法(Selection Sort) 挑選排序法也是透過「鍵值交換」來達成排序的目的。 第1回合從n筆鍵值中挑選出最小的鍵值，然後將它與d[0]交換位置。 第2回合從剩下的n-1筆鍵值中挑選出最小的鍵值，然後將它與d[1]交換位置。 第3回合從剩下的n-2筆鍵值中挑選出最小的鍵值，然後將它與d[2]交換位置。 第n-1回合從剩下的2筆鍵值中挑選出最小的鍵值，然後將它與d[n-2]交換位置。 剩下的1筆鍵值便是所有鍵值中的最大者，它自然存放在d[n-1]位置。 資料結構導論 - C語言實作

8.3.2. 挑選排序法(Selection Sort) 採用挑選排序法將編號為0、1、2、...、n-1的n筆紀錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆紀錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號紀錄的鍵值、d[1]儲存第1號紀錄的鍵值、…、d[n-1]儲存第n-1號紀錄的鍵值。 步驟2：重複執行步驟3，共計n-1回合。 步驟3：第i回合(i從1開始)，從陣列d[i-1]至d[n-1]中找出最小的鍵值(設d[x])，然後將d[x]與d[i-1]之鍵值交換。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]之值。 資料結構導論 - C語言實作

8.3.2. 挑選排序法(Selection Sort) 【例1】挑選排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值{83，66，55，21，88，18，88*，99}已經儲存在一維陣列d[8]中。 如果我們採用「挑選排序法」來將該組資料依「鍵值不遞減」的順序排序，總共須要7個回合，每一回合排序後之結果詳如表8.2所示。 資料結構導論 - C語言實作

8.3.2. 挑選排序法(Selection Sort)

8.3.2. 挑選排序法(Selection Sort) 第1回合， 從d[0]到d[7]找出最小者，結果找到d[5]=18最小，將d[5]之值與d[0]之值交換。 本回合排序後，最小之鍵值已經被安排到d[0]位置。 第2回合， 從d[1]到d[7]找出最小者，結果找到d[3]=21最小，將d[3]之值與d[1]之值交換。 本回合排序後，第2小之鍵值已經被安排到d[1]位置。 第3回合， 從d[2]到d[7]找出最小者，結果找到d[2]=55最小，將d[2]之值與d[2]之值交換。 本回合排序後，第3小之鍵值已經被安排到d[2]位置。 資料結構導論 - C語言實作

8.3.3. 插入排序法(Insertion Sort) 插入排序法的觀念是將n筆鍵值區分成「已排序」和「未排序」的A、B兩群 A群：已經排序好了 B群：尚未排序 排序時從B群取出一筆資料然後將之插入到A群的正確位置，重複這個動作直到B群空無資料，此時A群便是完整排序的資料了。 資料結構導論 - C語言實作

8.3.3. 插入排序法(Insertion Sort) 資料結構導論 - C語言實作

8.3.3. 插入排序法(Insertion Sort) 採用插入排序法將編號為0、1、2、...、n-1的n筆紀錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆紀錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號紀錄的鍵值、d[1]儲存第1號紀錄的鍵值、…、d[n-1]儲存第n-1號紀錄的鍵值。 步驟2：重複執行步驟3共計n-1回合。 步驟3：第i回合(i從1開始)，將陣列d[i]插入到其前面d[0]至d[i-1]的正確位置。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]之值。 資料結構導論 - C語言實作

8.3.3. 插入排序法(Insertion Sort) 【例1】插入排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99} 已經儲存在一維陣列d[8]中。 如果我們採用「插入排序法」來將該組資料依「鍵值不遞減」的順序排序，總共須要7個回合，每一回合排序後之結果詳如表8.3所示。 資料結構導論 - C語言實作

8.3.3. 插入排序法(Insertion Sort) 【例1】插入排序法 一開始， A群={83}， B群={66，55，21，88，18，88*，99}。 第1回合， 將B群的第1個鍵值d[1](66)插入A群，且必須保持A群的鍵值均按「不遞減」的順序排列。 因此66必須放到83之前，即d[0]=66，d[1]=83， 完成後A群={66，83}， B群={55，21，88，18，88*，99}。 資料結構導論 - C語言實作

8.3.3. 插入排序法(Insertion Sort) 資料結構導論 - C語言實作

8.3.4. 謝耳排序法(Shell Sort) 利用「固定間格」將部分鍵值先進行一次粗略的排序。 挑選一個固定的間距值s，然後將待排序的n筆鍵值分割成s組，每一群組裡的鍵值是從原始n個鍵值中挑出相間隔s間距的鍵值而成。 可減少插入排序法的資料搬動次數。 資料結構導論 - C語言實作

8.3.4.  謝耳排序法(Shell Sort) 採用謝耳排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆記錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號記錄的鍵值、d[1]儲存第1號記錄的鍵值、…、d[n-1]儲存第n號記錄的鍵值。 步驟2：設定一適當之s值。(最好選用質數來當作 s值) 資料結構導論 - C語言實作

8.3.4.  謝耳排序法(Shell Sort) 步驟3：分組，將陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]均勻地分成s組，且同一組內的陣列元素之間距均為s，分配結果如下： 令a = (n-1)/s。 第1組 = {d[0]，d[s]，s[2×s]，...，A[a×s]}。 第2組 = {d[1]，d[1+s]，s[1+2×s]，...， A[1+a×s]}。 第3組 = {d[2]，d[2+s]，s[2+2×s]，...，A[2+a×s]}。 ‧‧‧ 第s組 = {d[s-1]，d[2×(s-1)]，s[3×(s-1)]，...。 資料結構導論 - C語言實作

8.3.4.  謝耳排序法(Shell Sort) 步驟4：使用插入排序法分別針對第1組、第2組、第3組、...、第s組進行「鍵值不遞減」排序。 步驟5：重新排列，將每一組的第1個值、第2個鍵值、第3個鍵值、...重新排列到d[0]、d[1]、d[2]、…、d[n-1]位置。 步驟6：重新設定一個較小的s值。若s>0則回到步驟3。 步驟7：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-i]之值。 資料結構導論 - C語言實作

8.3.4. 謝耳排序法(Shell Sort) 【例1】謝耳排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值分別為 {83，66，55，21，88，18，88*，99}， 並且已經儲存在一維陣列d[8]中。 採用「謝耳排序法」來將該組資料依「鍵值不遞減」的順序排序之過程如下： 第1回合，我們假設s=3，將8個鍵值區分成3組。每一個組最多有3個鍵值，最少有2個鍵值。 第1組鍵值={d[0]、d[3]、d[6]}={83、21、88*}。 第2組鍵值={d[1]、d[4]、d[7]}={66、88、99}。 第3組鍵值={d[2]、d[5]}={55、18}。 資料結構導論 - C語言實作

8.3.4. 謝耳排序法(Shell Sort) 使用插入排序法分別對第1組、第2組、第3組鍵值進行排序，結果為： 第1組鍵值={21、83、88*}。 第2組鍵值={66、88、99}。 第3組鍵值={18、55}。 重新排列，將每一組的第1個鍵值，分別放入d[0]、d[1]、 d[2]。將每一組的第2個鍵值，分別放入d[3]、d[4]、 d[5]。將每一組的第3個鍵值，分別放入d[6]、d[7]，得到： 資料結構導論 - C語言實作

8.3.4. 謝耳排序法(Shell Sort) 第2回合，令s=s-1=3-1=2，將8個鍵值區分成2組。 第1組鍵值={d[0]、d[2]、d[4]、d[6]}={21、18、88、88*}。 第2組鍵值={d[1]、d[3]、d[5]、d[7]}={66、83、55、99}。 使用插入排序法分別對第1組、第2組鍵值進行排序，結果為： 第1組鍵值={18、21、88、88*}。 第2組鍵值={55、66、83、99}。 資料結構導論 - C語言實作

8.3.4. 謝耳排序法(Shell Sort) 第3回合，令s=s-1=2-1=1，直接用插入排序法對陣列d的鍵值排序，得到： 資料結構導論 - C語言實作

8.3.5.  快速排序法(Quick Sort) 採用插入排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆紀錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號紀錄的鍵值、d[1]儲存第1號紀錄的鍵值、…、d[n-1]儲存第n-1號紀錄的鍵值。 步驟2：設d[low]至d[high]為本次待排序的資料範圍(low < high)。 令K= d[low]。 步驟3：從左(d[low+1])向右(d[high])找出一個鍵值Ki=d[i]，滿足Ki  K。(若Ki不存在，則令i=high+1)。 資料結構導論 - C語言實作

8.3.5.  快速排序法(Quick Sort) 步驟4：從右(d[high])向左(d[low])找出一個鍵值Kj=d[j]，滿足Kj ≤ K。(若Kj不存在，則令j=low)。 步驟5：若i < j，則將Ki 與Kj交換，然後跳到步驟2。 步驟6：若i  j則將K與Kj交換，並以j為分割點將待排序的鍵值範圍(d[low]至d[high])分割成左右兩半，即： 左半邊 = {d[low]、d[low+1]、d[low+2]、...、 d[j-1]}。 右半邊 = {d[j+1]、d[j+2]、d[j+3]、...、 d[high]}。 步驟7：再分別針對左右兩半邊遞迴地執行步驟2-6，直到low = high(即只剩下一個鍵值)為止。 步驟8：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]之值。 資料結構導論 - C語言實作

8.3.5. 快速排序法(Quick Sort) 【例1】快速排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99} 已經儲存到一維陣列d[8]中。 如果我們採用「快速排序法」來將該組資料依「鍵值不遞減」的順序排序，每一回合排序處理過程詳如表8.8所示。 資料結構導論 - C語言實作

8.3.5. 快速排序法(Quick Sort) 步驟1， 排序範圍為d[0]至d[7]，即low=0，high=7。 K=d[0]=83，從d[0]往右(d[7])找出 Ki  K，結果找到Ki=K4=d[4]=88  83。 從d[7]往左(d[0])找出Kj ≤ K，結果找到Kj=K5=d[5]=18 ≤ 83。 因i < j，將Ki 與 Kj交換(即d[4]=88與d[5]=18交換)， 得到d[4]=18，d[5]=88。結果如表8.8步驟2所示。 資料結構導論 - C語言實作

8.3.5. 快速排序法(Quick Sort) 步驟2， 排序範圍還是d[0]至d[7]，即low=0，high=7。 K=d[0]=83，從d[0]往右(d[7])找出 Ki  K，結果找到Ki=K5=d[5]=88  83。 從d[7]往左(d[0])找出Kj ≤ K，結果找到Kj=K4=d[4]=18 ≤ 83。 因i > j，將K 與 Kj交換(即d[0]=83與d[4]=18交換)， 得到d[0]=18，d[4]=83。結果如表8.8步驟3所示。 資料結構導論 - C語言實作

8.3.5. 快速排序法(Quick Sort) 步驟3， 其餘詳細步驟，請參閱課本表8.8 以d[j]=d[4]=83為分割點，將待排序的資料範圍分割成左半邊(即d[0]到d[3])和右半邊(即d[5]到d[7])， 結果如表8.8步驟3所示。 其餘詳細步驟，請參閱課本表8.8 資料結構導論 - C語言實作

8.3.5.  快速排序法(Quick Sort) 資料結構導論 - C語言實作

資料結構導論 - C語言實作

8.3.6. 樹排序法 (Tree Sort) 二元搜尋樹(Binary Search Tree) 二元搜尋樹中的任一節點其左子樹的節點鍵值一定比它小 其右子樹的節點鍵值一定大於或等於它 資料結構導論 - C語言實作

8.3.6.  樹排序法 (Tree Sort) 採用樹排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：輸入n筆鍵值，以鍵值為樹的節點來建造一棵二元搜尋樹。即： 以第1個輸入的鍵值為樹根。 對於第2個鍵值到第n個鍵值執行下列動作： a.  從樹根開始比較大小，若比樹根小 則往左子樹繼續比較，否則往右子 樹繼續比較。 b.  當遇到樹葉節點，若比樹葉節點小 則放在左子樹，否則放在右子樹。 步驟2：以中序法追蹤所得即為按鍵值不遞減之排序結果。 資料結構導論 - C語言實作

8.3.6. 樹排序法 (Tree Sort) 【例1】樹排序法(Tree Sort) 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值為： {83，66，55，21，88，18，88*，99}。 步驟1，輸入鍵值 {83，66，55，21，88，18，88*，99}， 並建造出一棵二元搜尋樹。 資料結構導論 - C語言實作

8.3.6.  樹排序法 (Tree Sort) 資料結構導論 - C語言實作

8.3.6. 樹排序法 (Tree Sort) 步驟2，用中序法追蹤二元搜尋樹即可得到按鍵值不遞減之排序結果，即： 18、21、55、66、83、88、88*、99 資料結構導論 - C語言實作

8.3.7. 堆積排序法(Heap Sort) 完整二元樹須滿足以下條件： 完整二元樹是一棵二元樹。 完整二元樹的建立須先有左子樹然後才有右子樹。 完整二元樹的樹葉節點，頂多相差1個階度。 資料結構導論 - C語言實作

8.3.7. 堆積排序法(Heap Sort) 圖8.7即是一個含有8個節點的完整二元樹 其中0、1、2、3、...、7為節點之編號，也是建造完整二元樹的順序，而 K0、K1、K2、K3、...、K7為樹中節點所儲存之鍵值。 資料結構導論 - C語言實作

8.3.7. 堆積排序法(Heap Sort) 堆積樹須滿足以下條件： 是一棵完整二元樹(或完滿二元樹)。 每一個節點之鍵值大於或等於其子節點之鍵值。 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 採用堆積排序法將編號為0、1、2、...、n-1的n筆記錄之鍵值{K0，K1，K2，…，Kn-1}，按照「鍵值不遞增」的順序加以排列的步驟如下： 步驟1：以鍵值{K0，K1，K2，…，Kn-1}建造出完整二元樹(如圖8.7之結構)，如果用陣列d[n]來儲存完整二元樹，則d[0]=K0，d[1]=K1，d[2]=K2，d[3]=K3，...，A[n-1]=Kn-1。 步驟2：將完整二元樹轉換成對應的堆積樹。 步驟3：將樹根砍下來並輸出樹根之鍵值。 資料結構導論 - C語言實作

8.3.7. 堆積排序法(Heap Sort) 步驟4：將堆積樹的最後一個節點(即編號最大的節點)搬到樹根位置成為新的樹根節點。 步驟5：如果只剩樹根節點則輸出樹根之鍵值，結束。否則，重建堆積樹，然後回到步驟3。 資料結構導論 - C語言實作

8.3.7. 堆積排序法(Heap Sort) 【例1】堆積排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99}， 我們要將這一組資料依照鍵值不遞增(Non-increasing Order)之順序加以排序，其過程如下： 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 步驟1： 以鍵值{83，66，55，21，88，18，88*，99}建造出一棵完整二元樹，即： 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 步驟2： 將完整二元樹轉換成對應的堆積樹。其方法是從樹根(節點0)開始，對於所有非樹葉節點，做以下處理： 步驟2.1： 檢查其鍵值是否大於或等於其左子樹根之鍵值，若是，則執行驟2.2，否則須與左子樹根之鍵值交換(對調)。 步驟2.2： 檢查其鍵值是否大於或等於其右子樹根之鍵值，若是，則執行驟2.3，否則須與右子樹根之鍵值交換。 步驟2.3： 檢查其鍵值是否大於其父節點之鍵值，若是，則須與父節點之鍵值交換(對調)，並繼續遵此原則追朔至樹根為止。 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 步驟3： 開始排序，參考圖8.10(1)，輸出樹根之鍵值99，然後將最後一號節點之鍵值21搬到樹根位置，成為圖8.10(2)。接著，重建堆積樹，就是將樹根節點之鍵值調整到正確的位置上，得到圖8.10(3)。 同樣地，輸出樹根之鍵值88，然後將最後一號節點之鍵值55搬到樹根位置，成為圖8.10(4)。接著，重建堆積樹，得到圖8.10(5)。 其餘排序過程詳如圖8.10(6)至圖8.10(13)。我們得到之排序結果為： 99、88、88*、83、66、55、21、18。 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 資料結構導論 - C語言實作

8.3.7.  堆積排序法(Heap Sort) 資料結構導論 - C語言實作

8.3.8.  合併排序法(Merge Sort) 2-路合併 3-路合併 ... k-路合併 資料結構導論 - C語言實作

8.3.8.  合併排序法(Merge Sort) 採用合併排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆記錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號記錄的鍵值、d[1]儲存第1號記錄的鍵值、…、d[n-1]儲存第n-1號記錄的鍵值。將d[i]視為長度為1的鍵值。 步驟2：第i回合，將 個長度為i的鍵值，兩兩合併，成為 個長度為2i的鍵值組。 步驟3： i=i+1，重複執行步驟1，直到合併成1組長度為n的鍵值組為止。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-i]之值。 資料結構導論 - C語言實作

8.3.8.  合併排序法(Merge Sort) 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 【例1】2-路合併排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值{83，66，55，21，88，18，88*，99}已經儲存在一維陣列d[8]中，共計8個鍵值。 第1回合，{83}與{66}合併排序，{55}與{21}合併排序，{88}與{18}合併排序，{88*}與{90}合併排序。得到4組長度為2的鍵值組，即{66、83}、{21、55}、{18、88}、{88*、90}。 第2回合，{66、83}與{21、55}合併排序，{18、88}與{88*、90}合併排序。得到2組長度為4的鍵值組，即{21、55、66、83}、{18、88、88*、90}。 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 又稱為「桶(箱)子」排序法。 根據待排序的鍵值之「個別位數(Digit)」進行處理以獲得排序的結果。 最有效鍵優先(Most Significant Digit First：MSD) 從鍵值最左邊的位數開始處理，採用 「分配」、「排序」、「收集」等三個步驟。 最無效鍵優先(Least Significant Digit First：LSD) 從鍵值最右邊的位數開始處理，採用 「分配」和「收集」兩個步驟。 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 【例1】基數排序法－最無效鍵優先(LSD)，按「鍵值不遞減」排序 假設有一組未經排序的資料R0、R1、R2、...、R10、R11，其鍵值為： {185，66，221，88，700，88*，9，1，123，8765，917，2}。 第0號鍵值185，表示有三個位數，即1、8和5。 倒數第3個鍵值8765，則表示有四個位數，即8、7、6和5。 採用LSD排序法將上述鍵值按「鍵值不遞減」之順序來列的處理步驟如下： 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 步驟1：準備好10個箱子，編號分別為0，1，2，…，9。 步驟2：(第1回合)依據鍵值的「個位數」將鍵值{185，66，221，88，700，88*，9，1，123，8765，917，2}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 步驟3：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 700，221，1，2，123，185，8765，66，917，88，88*，9 步驟4：(第2回合)依據鍵值的「十位數」將鍵值{700，221，1，2，123，185，8765，66，917，88，88*，9}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 步驟5：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 700，1，2，9，917，221，123，8765，66，185， 88，88* 步驟6：(第3回合)依據鍵值的「百位數」將鍵值{700，1，2，9，917，221，123，8765，66，185，88，88*}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 步驟7：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 1，2，9，66，88，88*，123，185， 221，700，8765，917 步驟8：(第4回合)依據鍵值的「千位數」將鍵值{1，2，9，66，88，88*，123，185，221，700，8765，917}一一「分配」到相同編號的箱子中，所得之結果如下： 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 步驟9：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 1，2，9，66，88，88*，123，185， 221，700，917，8765 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 【例2】基數排序法－最有效鍵優先(MSD)，按「鍵值不遞減」排序 假設有一組未經排序的資料R0、R1、R2、...、R10、R11，其鍵值為： {18，66，55，61，21，88，10，88*，99，91，28，51}。 採用MSD排序法將上述鍵值按「鍵值不遞減」之順序來列的處理步驟如下： 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 步驟1：準備好10個箱子，編號分別為0，1，2，…，9。 步驟2：(第1回合)依據鍵值的「十位數」將鍵值{18，66，55，61，21，88，10，88*，99，91，28，51}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作

8.3.9. 基數排序法(Radix Sort) 步驟3：將每一號箱子內之鍵值，分別利用插入法排序按鍵值不遞減排序，所得到的結果如下： 步驟4：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 10，18，21，28，51，55，61，66，88， 88*，91，99 資料結構導論 - C語言實作

8.3 外部排序法(External Sort) 當待排序的鍵值數量大到超過記憶體的容量時 須借助於磁碟、磁帶等輔助記憶體來暫存排序過程中的部分結果。 這種利用外部儲存媒體的排序動作為「外部排序」。 k-路合併排序法。 資料結構導論 - C語言實作

8.4 效益評估 排序法大都脫離不了三個基本動作： 衡量因素： 比較。 交換位置。 重新分配位置。 最壞的情況下所須的時間(或比較次數)。 平均情況下所須的時間(或比較次數)。 排序過程中所須要的額外記憶體空間。 資料結構導論 - C語言實作

8.4 效益評估 各種排序法都有其優點與缺點： 快速排序法雖然處理速度非常快，但在最壞的情況下排序的效率與氣泡浮昇排序法、挑選排序法、插入排序法都是O(n2)。 氣泡浮昇排序法、挑選排序法、插入排序法的效率都不是很好，但程式很容易撰寫，當鍵值數量較少或部份鍵值已經排序好時效果也不差。 資料結構導論 - C語言實作

8.4 效益評估 各種排序法都有其優點與缺點： 基數排序法的LSD排序方式，平均而言效益最佳，但不適合負數之排序。而其最大的缺點是須要許多額外的記憶體空間，不信的話可以拿文字串來排序看看。 堆積排序法在最壞的情況下優於快速排序法。但在平均情況下比快速排序法稍慢一些，因為第一次建立堆積樹須額外花費一些時間。又快速排序法所須的額外記憶體多於堆積排序法。 資料結構導論 - C語言實作

8.4 效益評估 資料結構導論 - C語言實作

8.4 效益評估 資料結構導論 - C語言實作