第8章 資料排序 資料結構設計與C++程式應用

Presentation on theme: "第8章 資料排序 資料結構設計與C++程式應用"— Presentation transcript:

1 第8章 資料排序 資料結構設計與C++程式應用
Fundamentals of Data Structures and Their Applications Using C++ 第8章 資料排序 資料結構設計與C++程式應用 版權所有 禁止重製

2 排序的基本觀念 檔案(File) 記錄(Row或Record) 欄位(Column或Field) 鍵值(Key Value)

3 內部排序法(Internal Sort) 氣泡浮昇排序法(Bubble Sort) 選擇排序法(Selection Sort)
插入排序法(Insertion Sort) 謝耳排序法(Shell Sort) 快速排序法(Quick Sort) 累堆排序法(Heap Sort) 合併排序法(Merge Sort) 基數排序法(Radix Sort)或稱為筒子排序法(Bucket Sort) 樹排序法 (Tree Sort)

4 內部排序法(Internal Sort) 氣泡浮昇排序法(Bubble Sort)
將N筆記錄(編號0至N-1)按鍵值不遞減次序排序的氣泡浮昇排序法 1.重複步驟2 N-1回合，直到其中有一回合沒有「交換」情形發生 為止。 2.比較陣列中相鄰兩元素之鍵值，若前面元素大於後面元素， 則立刻將兩元素值交換。

5 內部排序法(Internal Sort) 氣泡浮昇排序法(Bubble Sort) 氣泡浮昇排序法之每一回合結果

6 內部排序法(Internal Sort) 選擇排序法(Selection Sort)
將N筆記錄(編號1至N)按鍵值不遞減次序排序的選擇排序法為： 1. 重複步驟2 N-1回合。 2.找出第i個至第N個鍵值中的最小者，並將之與第i個鍵值交換。 其中i等於回合數。 選擇排序法的每一回合結果

7 內部排序法(Internal Sort) 插入排序法(Insertion Sort)
將N筆記錄(編號1至N)依鍵值不遞減之次序排序的插入排序法為： 1. 從第2個鍵值至第N個鍵值，分別執行步驟2。 2.將該鍵值插入到其前面所有鍵值當中第一個大於本身的鍵值之前， 若沒有大於本身者，則保持原狀並繼續下一回合。 插入排序法每一回合排序前，已排序/未排序鍵值分佈

8 內部排序法(Internal Sort) 插入排序法(Insertion Sort) 插入排序法的每一回合結果

9 內部排序法(Internal Sort) 謝耳排序法(Shell Sort)
將N筆記錄(編號0至N-1)按鍵值不遞減之順序排列之謝耳排序法為： 1. 選擇一適當S值(S最好為質數)。 2.重複步驟3、4直到S值等於1為止。 3.將陣列A中的N個鍵值均勻地分成S組且同一組內陣列元素之間距均 為 S，分配結果如下： 第一組：(A[0]，A[S]，A[2S]，...，A[ (N-1)/S*S ]) 第二組：(A[1] ，A[S+1]，A[2S+1]，...， A[ (N-1)/S*S+1 ]) … 第 S組：(A[S-1]，A[2S-1]，A[3S-1]，…，A[N-1]) 然後，每一分組皆用插入排序法排序之。 4.令 S 等於 S 的前一個質數，跳回步驟 2。(註：本步驟只要 S 值 遞減即可，不一定要為質數)

10 內部排序法(Internal Sort) 謝耳排序法(Shell Sort) 原始記錄鍵值： 第一回合，令 S=3

11 內部排序法(Internal Sort) 謝耳排序法(Shell Sort) 第二回合，令 S=S-1=2

12 內部排序法(Internal Sort) 快速排序法(Quick Sort) 分而治之(Divide and Conquer)
觀念：將待排序的N個鍵值(編號0至N-1)分成左右兩半，左半邊之 鍵值小於第一個鍵值(即a[0])，而右半邊則大於或等於第一個 鍵值，如下圖所示 將A[L]與A[J]之鍵值交換

13 內部排序法(Internal Sort) 快速排序法(Quick Sort)
將N筆記錄(編號0至N-1)按鍵值不遞減之順序排列之快速排序法為： 1. 令K=待排序範圍之第一個(最左邊)鍵值。(第一次為A[0])。 2.由左向右找出一個鍵值Ki，滿足Ki > K。 。 3.由右向左找出一個鍵值Kj，滿足Kj < K。 4.若i < j則將Ki 與Kj交換，然後跳到步驟2。 5.若i ≧ j則將K與Kj交換，並以j為基準分割成左右兩半，然後分別 針對左右兩半進行步驟1至5，直到左半邊鍵值 = 右半邊鍵值為止。

14 內部排序法(Internal Sort) 快速排序法(Quick Sort)

15 內部排序法(Internal Sort) 堆積排序法(Heap Sort) 完整二元樹(Complete Binary Tree)
1.是一個二元樹。 2.先有左子樹再有右子樹。 3.從樹根節點到每一個樹葉節點之路徑所經過之節點個數頂多差 1。 堆積樹(Heap Tree) 1.堆積樹除了是一個完整二元樹。 2.每一個節點之鍵值大於或等於其子節點之鍵值。 3.因此樹根節點之鍵值是堆積樹中之最大者。

16 內部排序法(Internal Sort) 堆積排序法(Heap Sort)
將N筆記錄鍵值K0，K1，K2，…，KN-1，依鍵值由大到小不遞增之順序排列之堆積排序法為： 1.將K0，K1，K2，…，KN-1，轉換成完整二元樹 2.將完整二元樹轉換成堆積樹。 3.輸出樹根鍵值。 4.將樹中最後一個節點搬到樹根。 5.重複步驟2、3、4直到輸出所有鍵值為止。

17 內部排序法(Internal Sort) 堆積排序法(Heap Sort)
將鍵值 {51，67，5，21，78，35，21+，1} 按鍵值不遞增排序之堆積排序過程如下： 1.將鍵值轉換成完整二元樹。 2.將完整二元樹轉換成堆積樹。

18 內部排序法(Internal Sort) 堆積排序法(Heap Sort)

19 內部排序法(Internal Sort) 堆積排序法(Heap Sort) 3.輸出樹根鍵值。 4.將樹中最後一個節點搬到樹根。
5.重複步驟2、3、4直到輸出所有鍵值為止。

20 內部排序法(Internal Sort) 堆積排序法(Heap Sort)

21 內部排序法(Internal Sort) 堆積排序法(Heap Sort)

22 內部排序法(Internal Sort) 堆積排序法(Heap Sort)

23 內部排序法(Internal Sort) 合併排序法(Merge Sort) ： 是一個典型的「分而治之」方法。
1.將N個長度為1的鍵值成對地合併成N/2個長度為2的鍵值組。 2.將N/2個長度為2的鍵值組成對地合併成N/4個長度為4的鍵值組。 3.將鍵值組成對地合併，直到合併成1組長度為N的鍵值組為止。

24 內部排序法(Internal Sort) 合併排序法(Merge Sort) ：
將鍵值 {2，14，8，21，8+，37，89} 按鍵值不遞減順序排序之合併排序法的三個回合如下：

25 內部排序法(Internal Sort) 基數排序法(Radix Sort)
又稱多鍵排序(Multi-Key Sort)、箱子排序法(Bucket Sort) 最有效鍵優先(Most Significant Digit First：MSD) 1. 從最左邊的位數開始比較。 2. 是採用「分配」、「排序」、「收集」等三個步驟進行。 最無效鍵優先(Least Significant Digit First：LSD) 1.從最右邊的位數開始。 2.只須採用「分配」和「收集」兩個步驟。

26 內部排序法(Internal Sort) 基數排序法(Radix Sort)
利用MSD法排序{A1，C3，A10，D6，B12，C7，A3，B8，D9，C2，B13，A5，C11等13張牌的過程為： 步驟 1. 準備A、B、C、D四個箱子。 步驟 2. 依次讀入撲克牌，並依花色置入箱中，讀牌依序為A1，C3，…， C11。

27 內部排序法(Internal Sort) 基數排序法(Radix Sort)
步驟 3. A，B，C，D四個箱子內之牌，個別獨立用插入法排序。 步驟 4. 依A，B，C，D箱子的順序收集。 A1，A3，A5，A10，B8，B12，B13，C2，C3，C7，C11，D6，D9

28 內部排序法(Internal Sort) 基數排序法(Radix Sort)
利用LSD法排序{A1，C3，A10，D6，B12，C7，A3，B8，D9，C2，B13，A5，C11等13張牌的過程為： 步驟 1. 準備好13個箱子，編號為1，2，…，13。 步驟 2. 讀入撲克牌A1，C3，…，C11，並置入相同點數的箱中。

29 內部排序法(Internal Sort) 基數排序法(Radix Sort)
步驟 3. 按1、2、…、13箱子的順序收集 A1，C2，C3，A3，A5，D6，C7，B8，D9，A10，C11，B12，B13 請注意！目前已按點數由小到大排序好了。 步驟 4. 準備A，B，C，D四個箱子。

30 內部排序法(Internal Sort) 基數排序法(Radix Sort)
步驟 5. 依次讀入步驟3之結果A1，C2，C3，…，B13，並置入相同 花色的箱中 步驟 6. 依次從A、B、C、D箱子收集後即完成排序。 Al，A3，A5，A10，B8，B12，B13，C2，C3，C7，C11，D6，D9

31 內部排序法(Internal Sort) 基數排序法(Radix Sort)
利用LSD方式排列正整數鍵值{231，58，63，871，585，165，66}的過程如下： 步驟 1. 首先按個位數分配到相同的箱子中 收集後得到的順序為：231，871，63，585，165，66，58

32 內部排序法(Internal Sort) 基數排序法(Radix Sort) 步驟 2.按拾位數分配到正確的箱子中
收集後得到的順序為：231，58，63，165，66，871，585 步驟 3.最後按百位數來分配得到 收集之後即為所得：58，63，66，165，231，585，871

33 內部排序法(Internal Sort) 樹排序法(Tree Sort) 利用樹排序法將N筆記錄按鍵值不遞減的順序排序的方法如下：
1.首先依據鍵值大小建造成一棵二元搜尋樹(Binary Search Tree)， 即樹中的每一節點均滿足a.大於或等於左子樹根，b.小於或等於 右子樹根，因此： (1). 令第一個鍵值為樹根。 (2). 第二個到第N個鍵值依序建到樹中，即從樹根開始比， 若比樹根小則放到左子樹；否則放到右子樹。 2.以中序法追蹤所得即為排序結果。

34 內部排序法(Internal Sort) 樹排序法(Tree Sort)
以樹排序法將鍵值{33，78，11，48，20，55，33+，99}按不遞減順序排列的過程如下： 1. 建造成一棵二元搜尋樹。

35 內部排序法(Internal Sort) 樹排序法(Tree Sort)
2.以中序法追蹤得到 11，20，33，33+，48，55，78，99。

36 外部排序法(External Sort) K 路合併排序法(K Way Merge Sort) 行程(Runs) 2 路合併 Run1

37 排序法的效益評估