第10章、资料排序.ppt

1、1,第10章、資料排序,朝陽科技大學 王淑卿,2,大綱,氣泡浮昇排序法(Bubble Sort) 選擇排序法(Selection Sort) 插入排序法(Insertion Sort) 謝耳排序法(Shell Sort) 快速排序法(Quick Sort) 累堆排序法(Heap Sort) 合併排序法(Merge Sort) 基數排序法(Radix Sort)或稱為筒子排序法(Bucket Sort) 樹排序法 (Tree Sort),3,排序的基本觀念,檔案(File) 記錄(Row或Record) 欄位(Column或Field) 鍵值(Key Value),4,氣泡浮昇排序法(Bubbl

2、e Sort),將N筆記錄(編號0至N-1)按鍵值不遞減次序排序的氣泡浮昇排序法 1.重複步驟2 N-1回合，直到其中有一回合沒有交換情形發生為止2.比較陣列中相鄰兩元素之鍵值，若前面元素大於後面元素，則立刻將兩元素值交換,5,氣泡浮昇排序法(Bubble Sort),氣泡浮昇排序法之每一回合結果,氣泡浮昇排序法之每一回合結果,先定下來的為最大值,6,氣泡浮昇排序法(Bubble Sort),public class BubbleSort /ClassName and FileName:BubbleSortpublic static void main(String args) short s

3、ource = 48,11,9,78,9,20; /sourceshort exchange = 0;for (short pass = 1; pass sourcei + 1) exchange = sourcei; /swapsourcei = sourcei + 1;sourcei + 1 = exchange; / if end /for end /for endfor (short i = 0; i source.length; i+) System.out.print(sourcei + “ “); /show result on screen /main method end /

4、class end,7,選擇排序法(Selection Sort),將N筆記錄(編號1至N)按鍵值不遞減次序排序的選擇排序法為：1. 重複步驟2 N-1回合2.找出第i個至第N個鍵值中的最小者，並將之與第i個鍵值交換。 其中i等於回合數。,選擇排序法的每一回合結果,先定下來的為最小值,8,選擇排序法(Selection Sort),public class Arrays public static void selectionSort(int arr) int smallIndex, tmp; int pass, n = arr.length; / pass has the range 0 t

5、o n-2 for(pass=0; pass=n-2; pass+) smallIndex = pass; for(int i=pass; i=n-1; i+) if(arri=arrpass) smallIndex = i; if(smallIndex!=pass) tmp = arrpass; arrpass = arrsmallIndex; arrsmallIndex = tmp; ,public static void main(String args) / declare an integer array int arr = 87,38,77,38,25,21,1; Arrays.s

6、electionSort(arr); System.out.print(“Sorted: “); for(int i=0; i System.out.print(arri+“ “); ,9,插入排序法(Insertion Sort),將N筆記錄(編號1至N)依鍵值不遞減之次序排序的插入排序法為： 1. 從第2個鍵值至第N個鍵值，分別執行步驟22.將該鍵值插入到其前面所有鍵值當中第一個大於本身的鍵值之前，若沒有大於本身者，則保持原狀並繼續下一回合,插入排序法每一回合排序前，已排序/未排序鍵值分佈,10,插入排序法(Insertion Sort),插入排序法的每一回合結果,11,插入排序法(Ins

7、ertion Sort),輸入：整數陣列data，長度為n 輸出：排序陣列data，若itarget) 9 ,挑定一個target，向前比較,12,謝耳排序法(Shell Sort),將N筆記錄(編號0至N-1)按鍵值不遞減之順序排列之謝耳排序法為： 1. 選擇一適當S值(S最好為質數)2.重複步驟3、4直到S值等於1為止3.將陣列A中的N個鍵值均勻地分成S組且同一組內陣列元素之間距均為 S，分配結果如下：第一組：(A0，AS，A2S，.，A (N-1)/S*S )第二組：(A1 ，AS+1，A2S+1，.，A (N-1)/S*S+1 )第 S組：(AS-1，A2S-1，A3S-1，AN-1)

8、然後，每一分組皆用插入排序法排序之。4.令 S 等於 S 的前一個質數，跳回步驟 2。(註：本步驟只要 S 值遞減即可，不一定要為質數),13,謝耳排序法(Shell Sort),原始記錄鍵值：第一回合，令 S=3,14,謝耳排序法(Shell Sort),第二回合，令 S=S-1=2 最後，令S=1進行插入排序法得到：,15,謝耳排序法(Shell Sort),輸入：整數陣列data，共計n筆資料；ht, ht-1, ., h1(共t組)，且h1=1 輸出：排序陣列data，若itarget) 11 12 ,16,快速排序法(Quick Sort),分而治之(Divide and Conqu

9、er) 觀念：將待排序的N個鍵值(編號0至N-1)分成左右兩半，左半邊之鍵值小於第一個鍵值(即a0)，而右半邊則大於或等於第一個鍵值，如下圖所示將AL與AJ之鍵值交換,17,快速排序法(Quick Sort),將N筆記錄(編號0至N-1)按鍵值不遞減之順序排列之快速排序法為： 1. 令K=待排序範圍之第一個(最左邊)鍵值。(第一次為A0) 2.由左向右找出一個鍵值Ki，滿足Ki K3.由右向左找出一個鍵值Kj，滿足Kj K 4.若i j則將Ki 與Kj交換，然後跳到步驟2 5.若i j則將K與Kj交換，並以j為基準分割成左右兩半，然後分別針對左右兩半進行步驟1至5，直到左半邊鍵值 = 右半邊鍵

10、值為止,18,快速排序法(Quick Sort),快速排序法(Quick Sort),19,快速排序法(Quick Sort),輸入：整數陣列data,共n筆資料(data0datan-1),datan=MaxInt 輸出：排序陣列data，若ij，則dataidataj，0i,jn-1 1 void QuickSort (int data, int left, int right) 2 int i,j; 3 if (leftright) 4 i = left+1; 5 j = right; 6 target = dataleft; 7 do 8 while (dataitarget) i+;

11、 9 while (dataj=target) j+; 10 if(ij) swap(datai, dataj) 11 while (ij) 12 swap(dataleft,dataj) 13 QuickSort(data, left, j-1); 14 QuickSort(data, j+1, right); 15 16 ,20,堆積排序法(Heap Sort),堆積排序法(Heap Sort) 完整二元樹(Complete Binary Tree)1.是一個二元樹2.先有左子樹再有右子樹3.從樹根節點到每一個樹葉節點之路徑所經過之節點個數頂多差 1堆積樹(Heap Tree) 1.堆積樹

12、除了是一個完整二元樹2.每一個節點之鍵值大於或等於其子節點之鍵值3.因此樹根節點之鍵值是堆積樹中之最大者,21,堆積排序法(Heap Sort),將N筆記錄鍵值K0，K1，K2，KN-1，依鍵值由大到小不遞增之順序排列之堆積排序法為： 1.將K0，K1，K2，KN-1，轉換成完整二元樹 2.將完整二元樹轉換成堆積樹3.輸出樹根鍵值4.將樹中最後一個節點搬到樹根5.重複步驟2、3、4直到輸出所有鍵值為止,22,堆積排序法(Heap Sort),將鍵值 51，67，5，21，78，35，21+，1 按鍵值不遞增排序之堆積排序過程如下： 1.將鍵值轉換成完整二元樹2.將完整二元樹轉換成堆積樹,23,

13、堆積排序法(Heap Sort),24,堆積排序法(Heap Sort),3.輸出樹根鍵值4.將樹中最後一個節點搬到樹根5.重複步驟2、3、4直到輸出所有鍵值為止,25,堆積排序法(Heap Sort),26,堆積排序法(Heap Sort),27,堆積排序法(Heap Sort),28,堆積排序法(Heap Sort),演算法：傳出最小元素，更新最小堆積 輸入：整數陣列datas,datas+1,.,datat恰為最小堆積 輸出：傳出datas、並刪除之，剩下的ts筆資料存至datas,datas+1,.,datat-1中，且必須使成最小堆積1 void restore (int s, in

14、t t) 2 int x = datas; 3 int i=s, j; 4 datas = datat; 5 while (i=t/2) 6 if (data(2*i)data(2*i1) 7 j=2*i; 8 else 9 j=2*i1; 10 swap(datai, dataj); 11 i = j; 12 13,29,堆積排序法(Heap Sort),堆積排序 輸入：整數陣列data,共n筆資料(data0datan-1) 輸出：排序陣列data，若ij，則dataidataj，0i,jn-1 1 for (i=(n-1)/2; i=1; i-) do 2 restore(i, n);

15、3 for (i=n; i=1; i+)do; 4 輸出 data1; 5 data1 = datai; 6 restore(1, i-1); 7 ,30,合併排序法(Merge Sort),是一個典型的分而治之方法 將N筆記錄依鍵值不遞減順序排序之方法為：1.將N個長度為1的鍵值成對地合併成N/2個長度為2的鍵值組2.將N/2個長度為2的鍵值組成對地合併成N/4個長度為4的鍵值組3.將鍵值組成對地合併，直到合併成1組長度為N的鍵值組為止,31,合併排序法(Merge Sort),將鍵值 2，14，8，21，8+，37，89 按鍵值不遞減順序排序之合併排序法的三個回合如下：,32,演算法：合併

16、兩個已排序的數列 輸入：已排序陣列A，共m筆資料；已排序陣列B，共n筆資料 輸出：排序陣列C，若ij，則CiCj，0i,jm+n-11 void merge(int C, int k, int A, int i, int m, int B, int j, int n) 2 while (i=m) 10 ,合併排序法(Merge Sort),33,演算法：合併排序（遞迴版） 輸入：data陣列共計n筆資料 輸出：排序陣列data，若ij則dataidataj，0i,jn-11 int k=0; datan; 2 void merge_sort(int A, int left, int right

17、) 3 int i, j, k, m 4 if (leftright) 5 m = (left+right)/2; 6 merge_sort(A, left, m); 7 merge_sort(A, m+1, right); 8 merge(A, left, A, left, m, A, m+1, m) 9 10 11 main() 12 read_input_data(data, n); 13 merge_sort(data, 0, n-1); 14 ,合併排序法(Merge Sort),34,演算法：合併排序（非遞迴版） 輸入：data陣列共計n筆資料 輸出：排序陣列data，若ij，則d

18、ataidataj，0i,jn-1 1 main() 2 int len=2; 3 while (lenn) 4 for (i=0; in; i+=len) 5 merge(A,i,A,i,i+len/2-1,A,i+len/2,i+len/2-1); 6 len *= 2; 7 8 ,合併排序法(Merge Sort),35,基數排序法(Radix Sort),又稱多鍵排序(Multi-Key Sort)、箱子排序法(Bucket Sort)最有效鍵優先(Most Significant Digit First：MSD)1. 從最左邊的位數開始比較2. 是採用分配、排序、收集等三個步驟進行最

19、無效鍵優先(Least Significant Digit First：LSD) 1.從最右邊的位數開始2.只須採用分配和收集兩個步驟,36,基數排序法(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,分配,37,基數排序法(Radix Sort),步驟 3. A，B，C，D四個箱子內之牌，個別獨立用插入法排序 步驟 4. 依A，B，C，D箱子的順序收集。A1，A3，A5，A10，B

20、8，B12，B13，C2，C3，C7，C11，D6，D9,排序,收集,38,基數排序法(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，並置入相同點數的箱中。,分配,39,基數排序法(Radix Sort),步驟 3. 按1、2、13箱子的順序收集 A1，C2，C3，A3，A5，D6，C7，B8，D9，A10，C11，B12，B13請注意！目前已按點數由小到大排序好了。 步驟 4. 準備A，B，C，D四個箱

21、子。,收集,40,基數排序法(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,分配,收集,41,基數排序法(Radix Sort),利用LSD方式排列正整數鍵值231，58，63，871，585，165，66的過程如下：步驟 1. 首先按個位數分配到相同的箱子中 收集後得到的順序為：231，871，63，585，165，66，58,42,基數排序法(Radix Sort),步驟 2.按拾位數分配到正確的

22、箱子中 收集後得到的順序為：231，58，63，165，66，871，585步驟 3.最後按百位數來分配得到 收集之後即為所得：58，63，66，165，231，585，871,43,基數排序法(Radix Sort),輸入：整數陣列data,共n筆資料(data0datan-1), 輸出：排序陣列data，若imax) max = datai; 4 radix = log10 max /radix是max所擁有的位數; 5 for (i=1; i=radix; i+) 6 for (j=0; j10; j+) countj=0; 7 for (j=0; j10; j+) 8 digit =

23、dataj的第i位數字; 9 countdigit+; 10 11 index0=0; 12 for (j=1;j10;j+9) indexj=indexj-1+countj-1; 13 for (j=0; jn; j+) 14 digit = dataj的第i位數字; 15 tempindexdigit+ = dataj; 16 17 for(j=0; jn; j+) dataj = tempj; 18 ,44,樹排序法(Tree Sort),利用樹排序法將N筆記錄按鍵值不遞減的順序排序的方法如下： 1.首先依據鍵值大小建造成一棵二元搜尋樹(Binary Search Tree)，即樹中的每

24、一節點均滿足【大於或等於左子樹根】，【小於或等於右子樹根】，因此：(1). 令第一個鍵值為樹根(2). 第二個到第N個鍵值依序建到樹中，即從樹根開始比，若比樹根小則放到左子樹；否則放到右子樹 2.以中序法追蹤所得即為排序結果,45,樹排序法(Tree Sort),以樹排序法將鍵值33，78，11，48，20，55，33+，99按不遞減順序排列的過程如下： 1. 建造成一棵二元搜尋樹,46,樹排序法(Tree Sort),2.以中序法追蹤得到 11，20，33，33+，48，55，78，99,47,樹排序法(Tree Sort),/ / Binary_Tree_Sort.java / Binar

25、y Tree Sort / / Created by Kevin Bralten on 29/09/05. / Copyright (c) 2005 _MyCompanyName_. All rights reserved. / import java.util.*; public class Binary_Tree_Sort public static void main (String args) / inserted code here. long n=0; long t1 = 0, t2 = 0, t3 = 0, avg = 0,avgInsert = 0; int maxItems

26、= 5000000; int nRuns=10; int stepSize=50000; Random r=new Random(); Item root; LinkedList list; System.out.println(“n, total (ms), insert (ms)“); for(int k = 0; k = maxItems; k+=stepSize) / increment the number of items avg=avgInsert=0;,48,樹排序法(Tree Sort),for (int j = 0; j nRuns; j+) / To sort the A

27、rray 10 times to find the average list=new LinkedList(); t1 = System.currentTimeMillis(); root = new Item(r.nextInt(); for (int i = 1; i k; i+) root.addItem(r.nextInt(); ,t3 = System.currentTimeMillis(); root.toList(list); t2 = System.currentTimeMillis(); avg += (t2 - t1); avgInsert += (t3-t1); /Sys

28、tem.out.println(“Time for “ + k + “ items: “ +(avg/10) + “ms“); System.out.println(k+“, “+(avg/(float)nRuns) +“, “+(avgInsert/(float)nRuns); ,49,K 路合併排序法(K Way Merge Sort),行程(Runs) 2 路合併,Run2,Run3,Run4,Run2,50,K 路合併排序法(K Way Merge Sort),int num100; int ans100; int merge(int p,int r) if ( p = r )retu

29、rn 0; int i=p,j=(p+r)/2+1; merge(p,(p+r)/2); merge(p+r)/2+1,r); for (int k=0;k=numj ,51,排序法的效益評估,52,結論,排序(Sorting)，將一組資料一使用者需求，予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。排序後之資料，優點為容易閱讀、統計分析、與快速搜尋所要之資料。排序法分分類方式有三類： 第一類：內部與外部排序 內部排序(Internal Sort)又稱陣列排序。 【定義】排序之工作，主要在主記憶體(RAM)完成。 【適用時機】資料量較少者。 外部排序(External

30、Sort)又稱檔案排序。 【定義】排序之工作，主要是在輔助記憶體(Disk, File)完成。 【適用時機】資料量較大者。,53,結論,第二類：穩定與不穩定排序法 穩定排序法(Stable Sorting)，如果鍵值相同之資料，在排序後相對位置與排序前相同時，稱穩定排序。 【例如】 排序前：3,5,19,1,3*,10 排序後：1,3,3*,5,10,19 (因為兩個3, 3*的相對位置在排序前與後皆相同。) 不穩定排序法(Unstable Sorting)，如果鍵值相同之資料，在排序後相對位置與排序前不相同時，稱不穩定排序。 【例如】 排序前：3,5,19,1,3*,10 排序後：1,3*,

31、3,5,10,19 (因為兩個3, 3*的相對位置在排序前與後不相同。),54,結論,第三類：簡單與高等排序法 簡單排序法 【定義】排序演算法簡單，但執行時間較長。 【平均時間複雜度】 高等排序法 【定義】排序演算法複雜，執行時間較短。 【平均時間複雜度】 常見之排序演算法包括：氣泡排序、選擇排序、插入排序、快速排序、堆積(Heap)排序、薛爾(Shell)排序、合併排序、基數排序等，以下簡述之。,55,結論,氣泡排序(Bubble Sorting) 資料結構中最簡單之排序法。所謂氣泡排序法就是相臨資料互相比較，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將如氣泡般，依次由下往上浮

32、起。將N筆記錄(編號0至N-1)按鍵值不遞減次序排序的氣泡浮昇排序法： 重複步驟(2)N-1回合，直到其中有一回合沒有交換情形發生為止。 比較陣列中相鄰兩元素之鍵值，若前面元素大於後面元素，則立刻將兩元素值交換。,56,結論,選擇排序(Selection Sorting) 類似於氣泡排序法。主要差異在於，第n回合比較時，以一額外資料空間儲存目前第n大(小)，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將由最大(最小)逐回合比較至最小(最大)。將N筆記錄(編號1至N)按鍵值不遞減次序排序的選擇排序法為： 重複步驟(2)N-1回合。 找出第i個至第N個鍵值中的最小者，並將之與第i個鍵值

33、交換；其中i等於回合數。,57,結論,插入排序(Insertion Sorting) 每次往後拿一筆記錄，依大小插入已排序好的記錄。也就是說，差入一個記錄在一堆已排好序之記錄中。任何未排序前之第一筆資料可視為已排序好之資料。將N筆記錄(編號1至N)依鍵值不遞減之次序排序的插入排序法為： 從第2個鍵值至第N個鍵值，分別執行步驟(2)。 將該鍵值插入到其前面所有鍵值當中第一個大於本身的鍵值之前，若沒有大於本身者，則保持原狀並繼續下一回合。,58,結論,快速排序(Quick Sorting) 快速排序之觀念，找資料之中間值，將小於中間值放右邊，大於中間值放左邊，再以相同方法分左右兩邊序列，直到排序完

34、成。亦即將待排序的N個鍵值(編號0至N-1)分成左右兩半，左半邊之鍵值小於第一個鍵值(即a0)，而右半邊則大於或等於第一個鍵值。 取第一個記錄為鍵值K0，當中間值。由左而右找第一個Ki，使得KiK0。 由右而左找第一個Kj，使得KjK0。也就是說，從左邊找比K0大，從右邊找比K0小。 若ij則Ki與Kj對調位置繼續步驟(2)；否則K0與Kj對調位置，並以j為基準，分為兩個未排序之序列。 以遞迴呼叫方式對左右兩邊進行排序，直道完成排序。由最大(最小)逐回合比較至最小(最大)。,59,結論,堆積排序(Heap Sorting) 將N筆記錄鍵值K0，K1，K2，KN-1，依鍵值由大到小不遞增之順序排

35、列之堆積排序法為： 將K0，K1，K2，KN-1，轉換成完整二元樹。 將完整二元樹轉換成堆積樹。 輸出樹根鍵值。 將樹中最後一個節點搬到樹根 重複步驟(2)、(3)、(4)直到輸出所有鍵值為止。,60,結論,謝爾排序(Shell Sorting) 將N筆記錄(編號0至N-1)按鍵值不遞減之順序排列之謝耳排序法為： 選擇一適當S值(S最好為質數)。 重複步驟(3)、(4)直到S值等於1為止。 將陣列A中的N個鍵值均勻地分成S組且同一組內陣列元素之間距均為S，分配結果如下：第一組：(A0，AS，A2S，.，A (N-1)/S*S )第二組：(A1 ，AS+1，A2S+1，.，A (N-1)/S*S

36、+1 )第 S組：(AS-1，A2S-1，A3S-1，AN-1)然後，每一分組皆用插入排序法排序之。 令S等於S的前一個質數，跳回步驟(2)。(註：本步驟只要S值遞減即可，不一定要為質數),61,結論,合併排序(Merge Sorting) 是一個典型的分而治之方法，將N筆記錄依鍵值不遞減順序排序之方法為： 將N個長度為1的鍵值成對地合併成N/2個長度為2的鍵值組。 將N/2個長度為2的鍵值組成對地合併成N/4個長度為4的鍵值組。 將鍵值組成對地合併，直到合併成1組長度為N的鍵值組為止。,62,結論,基數排序(Radix Sorting) 又稱多鍵排序(Multi-Key Sort)、箱子排序法(Bucket Sort)，可分為最有效鍵優先(Most Significant Digit First：MSD)及最無效鍵優先(Least Significant Digit First：LSD)。 MSD的排序法為：從最左邊的位數開始比較。是採用分配、排序、收集等三個步驟進行 LSD的排序法為：從最右邊的位數開始。只須採用分配和收集兩個步驟。,