数据结构(c语言版)黄国瑜叶乃菁课件ch.ppt

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,黃國瑜、葉乃菁著,*,資料結構,第八章排序,黃國瑜、葉乃菁著,1,本章綱要,8-1 何謂排序?,8-2 內部排序法:交換式排序,8-2-1 氣泡排序法(,Bubble Sort),8-2-2,快速排序法(,Quick Sort),8-3,內部排序法:選擇式排序,8-3-1 選擇排序法(,Selection Sort),8-3-2,累堆排序法(,Heap Sort),黃國瑜、葉乃菁著,2,本章綱要,8-4,內部排序法:插入式排序,8-4-1 插入排序法(,Insertion Sort),8-4-2,謝耳排序法(,Shell Sort),8-4-3,二元樹排序法(,Binary-tree Sort),8-5,外部排序法：合併排序法(,Merge Sort),8-6,排序法的效率比較,黃國瑜、葉乃菁著,3,8-1何謂排序,排序,將一群資料依指定順序所進行的排列過程,排序後(由小到大),(由大到小),黃國瑜、葉乃菁著,4,8-1何謂排序,排序的特性,穩定性(,Stable):,排序過後能使值相同的資料，保持,原順序中之相對位置,不穩定性(,Unstable),黃國瑜、葉乃菁著,5,8-1何謂排序,例如:,原數列:,27.16.,9,(1),.31.7.24.,9,(2),.17,穩定性排序:,7.,9,(1),.,9,(2),.16.17.24.27.31,不穩定性排序:,7.,9,(2),.,9,(1),.16.17.24.27.31,黃國瑜、葉乃菁著,6,8-1何謂排序,排序的分類,內部排序(,Internal Sort),將欲處理的資料整個存放到內部記憶體中做排序，資料可被隨機存取。,(,a),交換式排序法,(,b),選擇式排序法,(,c),插入式排序法,黃國瑜、葉乃菁著,7,8-1何謂排序,排序的分類(,Con.),外部排序(,External Sort),欲處理的資料量過於龐大，無法全部存放到內部記憶體，必須借助外部輔助記憶體(,ex:,磁碟.磁帶)，資料不可隨機被存取。,(,a),合併排序法,(,b),直接合併排序法,黃國瑜、葉乃菁著,8,8-2 內部排序法：交換式排序,交換式排序,資料值比對後依判斷規則對資料位置進行交換,交換式排序法可分為兩種,氣泡排序法(,Bubble Sort),快速排序法(,Quick Sort),黃國瑜、葉乃菁著,9,8-2-1,氣泡排序法(,Bubble Sort),氣泡排序法,if (,左邊的值 右邊的值),then,此兩個值的位置互換,else /*,左邊的值 右邊的值*/,此兩個值的位置不變,右邊的值繼續和下一個值比較,黃國瑜、葉乃菁著,10,8-2-1,氣泡排序法(,Bubble Sort),例如:,data0 data3,共4個資料，共需比3回(6次),黃國瑜、葉乃菁著,11,8-2-1,氣泡排序法(,Bubble Sort),第1回(從,data0,比到,data3-4,個),比3次,Step1:,比較,data0 37 8,交換,交換結果：,黃國瑜、葉乃菁著,13,8-2-1,氣泡排序法(,Bubble Sort),第1回(,Con.),Step3:,比較,data2&data3,;,96 54,交換,交換結果：,黃國瑜、葉乃菁著,14,舉例說明:(Con.,舉例說明:(Con.,穩定性(Stable):排序過後能使值相同的資料，保持,舉例說明:(Con.,舉例說明:(Con.,外部排序(External Sort),(1)將欲排序的資料分別存在數個檔案大小可載入記憶,縮小為上一次分割間隔長度的二分之一,(4)直到分割間隔為零停止，則數列排序完成。,反覆掃瞄資料，速度不快也沒有效率,舉例說明:(Con.,(c)插入式排序法,空間複雜度:O(1),時間複雜度:O(n*log 2 n),r=2，指向data 4,8-2-1,氣泡排序法(,Bubble Sort),第2回(從,data0,比到,data2-3,個),比2次,Step1:,比較,data0,37 8,交換,交換結果：,黃國瑜、葉乃菁著,15,8-2-1,氣泡排序法(,Bubble Sort),第2回(從,data0,比到,data2-3,個),比2次,Step2:,比較,data1,37 54,不交換,黃國瑜、葉乃菁著,16,8-2-1,氣泡排序法(,Bubble Sort),第3回(從,data0,比到,data1-2,個),比1次,比較,data0&data1,;,8 37,不交換,黃國瑜、葉乃菁著,17,8-2-1,氣泡排序法(,Bubble Sort),優點:,若部分資料已排序，則可很快速完成排序,缺點:,反覆掃瞄資料，速度不快也沒有效率,穩定性排序法,參考程式,黃國瑜、葉乃菁著,18,8-2-2,快速排序法(,Quick Sort),快速排序法,假設有,n,個資料,data0 datan-1,設立指標,l=data0=k；,指向第1個位置,data0，i=0,指標,r=datan-1 ；,指向第,n,個位置,datan，j=n,黃國瑜、葉乃菁著,19,8-2-2,快速排序法(,Quick Sort),Step1,：l,往右找,直到找到比,l,值大時停止,假設停止於,datai,r,往左找,直到找到比,r,值小時停止,假設停止於,dataj,可能有兩種狀況：,if (i j)then,datai,和,dataj,的內容值交換,黃國瑜、葉乃菁著,20,8-2-2,快速排序法(,Quick Sort),Step1,:(Con.),if (i j)then,此陣列的第一個值和,dataj,的內容值交換,黃國瑜、葉乃菁著,21,8-2-2,快速排序法(,Quick Sort),Step2,：,每次被分割的區塊，再分別設立,l,及,r,指標，,l =,區塊第1個值，指向區塊第1個位置,r =,區塊最後1個值，指向(最後+1)的位置,Step3,：,各個區塊再個別進行,Step1，,直到所有區塊均,已排序完成。,(參考圖例),黃國瑜、葉乃菁著,22,8-2-2,快速排序法(,Quick Sort),舉例說明：,data0 data7,共8個資料,黃國瑜、葉乃菁著,23,8-2-2,快速排序法(,Quick Sort),舉例說明,:(,Con.),(1),l=data0=28，,指向,data0，i=0,r=datan-1=data7=17，,指向,data8，j=8,黃國瑜、葉乃菁著,24,8-2-2,快速排序法(,Quick Sort),舉例說明,:(,Con.),(2),l,往右找，直到找到28時停止，,i=2,r,往左找，直到找到17時停止，,j=7,i j (2 7),故,data2,和,data7,交換,黃國瑜、葉乃菁著,25,8-2-2,快速排序法(,Quick Sort),舉例說明,:(,Con.),(3),l,繼續往右，,r,繼續往左,i j (4 j (5 4),故,data0,和,data4,交換,黃國瑜、葉乃菁著,27,8-2-2,快速排序法(,Quick Sort),舉例說明,:(,Con.),(5),“28”,已找到其所屬的位置,並將陣列切割成兩部份,data0 data3：l=14，,指向,data 0,r=2，,指向,data 4,data5 data7：l=65，,指向,data 5,r=36，,指向,data 8,黃國瑜、葉乃菁著,28,8-2-2,快速排序法(,Quick Sort),舉例說明,:(,Con.),以表格的方式來表示排序的過程，中括號所包含部份為尚待排序的區塊,黃國瑜、葉乃菁著,29,8-2-2,快速排序法(,Quick Sort),不穩定性排序,空間複雜度,average case,:,介於,O(log,2,n),和,O(n),best case,:,O(log,2,n),worst case:,O(n),時間複雜度,average/best case,:,O(n*log,2,n),worst case:,O(n,2,),參考程式,黃國瑜、葉乃菁著,30,8-3 內部排序法：選擇式排序,選擇式排序,按指定的規則選出某一元素，經過和其他元素重整，交換位置後達到排序目的,選擇式排序法可分為兩種,選擇排序法(,Selection Sort),累堆排序法(,Heap Sort),黃國瑜、葉乃菁著,31,8-3-1,選擇排序法(,Selection Sort),選擇排序法,Step1:,以線性搜尋的方式找出最小的元素和第 一個元素交換,Step2:,從剩下的(,n-1),個資料中，找出最小的元 素和第二個元素交換,Step3:,以此類推,(參考圖例),黃國瑜、葉乃菁著,32,8-3-1,選擇排序法(,Selection Sort),舉例說明:,黃國瑜、葉乃菁著,33,8-3-1,選擇排序法(,Selection Sort),舉例說明,:(,Con.),(1),data0,和,data3,交換,黃國瑜、葉乃菁著,34,8-3-1,選擇排序法(,Selection Sort),舉例說明,:(,Con.),(2),data1,和,data4,交換,黃國瑜、葉乃菁著,35,8-3-1,選擇排序法(,Selection Sort),舉例說明,:(,Con.),(3),data2,和,data3,交換,黃國瑜、葉乃菁著,36,8-3-1,選擇排序法(,Selection Sort),舉例說明,:(,Con.),(4)排序完成,黃國瑜、葉乃菁著,37,8-3-1,選擇,排序法(,Selection Sort),優點:,最簡單的排序法,缺點:,所需的排序時間比其他排序法來的長,空間複雜度:,O(1)/O(n),時間複雜度:,O(n,2,),參考程式,黃國瑜、葉乃菁著,38,8-3-2,累堆排序法(,Heap Sort),累堆排序法,Step1:,將欲排序的,n,個值存入“陣列”,Step,2:將此二元樹建立成,max heap,Step3:,取出樹根(,root),的值，將剩下的值再排成,heap,Step4:,重覆,Step3,的動作，直到所有值均已輸出,(參考圖例),黃國瑜、葉乃菁著,39,8-3-2,累堆排序法(,Heap Sort),舉例說明:,Step1:,將欲排序的8個值”7 9 2 8 1 4 6 3”存入陣 列,其二元樹表示法為：,黃國瑜、葉乃菁著,40,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step2:,將此二元樹建立成,max heap (n=8,8/2=4,開始調整的節點索引值),(1)考慮,n,4,黃國瑜、葉乃菁著,41,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step2:(Con.),(2)考慮,n,3,黃國瑜、葉乃菁著,42,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step2:(Con.),(3)考慮,n,2,黃國瑜、葉乃菁著,43,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step2:(Con.),(4)考慮,n,1,黃國瑜、葉乃菁著,44,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step2:(Con.),(4)考慮,n,2,黃國瑜、葉乃菁著,45,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step2:(Con.),(4)考慮,n,4,黃國瑜、葉乃菁著,46,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step2:(Con.),(4)完成之,max heap,黃國瑜、葉乃菁著,47,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:,取出樹根(,root),的值，將剩下的值再排成,heap,”取出”並非真的是從陣列中刪除，而是和最後一個,節點交換,(1),黃國瑜、葉乃菁著,48,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:(Con.),(2),黃國瑜、葉乃菁著,49,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:(Con.),(3),黃國瑜、葉乃菁著,50,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:(Con.),(4),黃國瑜、葉乃菁著,51,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:(Con.),(5),黃國瑜、葉乃菁著,52,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:(Con.),(6),黃國瑜、葉乃菁著,53,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:(Con.),(7),黃國瑜、葉乃菁著,54,8-3-2,累堆排序法(,Heap Sort),舉例說明:(,Con.),Step3:(Con.),完成,heap sort,黃國瑜、葉乃菁著,55,8-3-2,累堆排序法(,Heap Sort),不穩定性排序,空間複雜度:,O(1),時間複雜度:,O(n*log,2,n),參考程式,黃國瑜、葉乃菁著,56,8-4 內部排序法：插入式排序,插入式排序,對於欲排序的元素以插入的方式找尋該元素的適當位置，以達到排序的目的,插入式排序法可分為兩種,插入排序法(,Insertion Sort),謝耳排序法(,Shell Sort),二元樹排序法(,Binary-tree Sort),黃國瑜、葉乃菁著,57,8-4-1,插入排序法(,Insertion Sort),插入排序法,假設欲排序的陣列元素,V,1,V,2,V,3,V,4,且,V,3,V,2,V,4,V,1,。,依序進行插入元素的動作，在每次插入時該,元素會放在適當的排序位置，直到最後一個,元素插入後，則所有元素排序完成。,(參考圖例),黃國瑜、葉乃菁著,58,8-4-1,插入排序法(,Insertion Sort),圖例:,假設欲排序的陣列元素,V,1,V,2,V,3,V,4,且,V,3,V,2,V,4,V,1,黃國瑜、葉乃菁著,59,8-4-1,插入排序法(,Insertion Sort),舉例說明:,欲排列數值 6,9,3,4,1,5,起始陣列：,黃國瑜、葉乃菁著,60,8-4-1,插入排序法(,Insertion Sort),舉例說明:(,Con.),Step1:,插入”9“：9 6,故9置於6之後,Step2:,插入”3“：3 6,故6.9往後移，3置於原6 的位置,黃國瑜、葉乃菁著,61,料排序好寫回檔案,(1)l=data0=28，指向data0，i=0,best case:O(n),average/best case:O(n*log 2 n),將欲處理的資料整個存放到內部記憶體中做排序，資料可被隨機存取。,8-4-3 二元樹排序法(Binary-tree Sort),8-4-2 謝耳排序法(Shell Sort),Step4:重覆 Step3 的動作，直到所有值均已輸出,舉例說明:(Con.,22 4 5,故6.9往後移，4置於 原6的位置,Step4:,插入”1“：1 3,故3.4.6.9均往後移，1 置於原3的位置,黃國瑜、葉乃菁著,62,8-4-1,插入排序法(,Insertion Sort),舉例說明:(,Con.),Step5:,插入”1“：1 5 6,故6.9往後移，5置於 原6的位置,黃國瑜、葉乃菁著,63,8-4-1,插入排序法(,Insertion Sort),穩定性排序,空間複雜度:,O(1),時間複雜度:,average/worst case :O(n*log,2,n),best case:,O(n),參考程式,黃國瑜、葉乃菁著,64,8-4-2,謝耳排序法(,Shell Sort),謝耳排序法,(1)將欲排序的數值依某個間隔長度分成數個,數列集合,(2)再針對各個數列集合進行插入法排序，,(3)重覆進行數列分割，每次分割的間隔長度,縮小為上一次分割間隔長度的二分之一,(4)直到分割間隔為零停止，則數列排序完成。,(參考圖例),黃國瑜、葉乃菁著,65,8-4-2,謝耳排序法(,Shell Sort),舉例說明:,黃國瑜、葉乃菁著,66,8-4-2,謝耳排序法(,Shell Sort),舉例說明:(,Con.),Step1,：,length=8/2=4,黃國瑜、葉乃菁著,67,8-4-2,謝耳排序法(,Shell Sort),舉例說明:(,Con.),Step2：length=4/2=2,黃國瑜、葉乃菁著,68,8-4-2,謝耳排序法(,Shell Sort),舉例說明:(,Con.),Step3：length=2/2=1,黃國瑜、葉乃菁著,69,8-4-2,謝耳排序法(,Shell Sort),穩定性排序,空間複雜度:,O(1),時間複雜度:,O(n,r,)1 r 2,參考程式,黃國瑜、葉乃菁著,70,8-4-3,二元樹排序法(,Binary-tree Sort,),二元樹排序法,1.將欲排序的元素一一以建立二元樹的方式插入，建,立二元樹需滿足二個條件：,(1)每一個節點最多只有兩個子節點(左節點、右節點),(2)若一節點有子節點，則該節點的資料要比左節點,的資料大，且比右節點的資料小(左節點,parent,右節點),2.使用二元樹中序走訪的方式將二元樹的節點列印出 來，即可得到元素的排序結果。,(參考圖例),黃國瑜、葉乃菁著,71,8-4-3,二元樹排序法(,Binary-tree Sort,),舉例說明:,欲排列陣列中的元素,Step1:,讀入”42”，為二元樹的樹根,42,15,61,22,54,38,黃國瑜、葉乃菁著,72,8-4-3,二元樹排序法(,Binary-tree Sort,),舉例說明:(,Con.),Step2,:讀入”15”，15 42，故插入為”42”的左節點,Step3:,讀入”61”，42 61，故插入為”42”的右節點,黃國瑜、葉乃菁著,73,8-4-3,二元樹排序法(,Binary-tree Sort,),舉例說明:(,Con.),Step4,:讀入”22”，22 42，往”42”的左子樹走,15 22,故插入為”15”的右節點,黃國瑜、葉乃菁著,74,8-4-3,二元樹排序法(,Binary-tree Sort,),舉例說明:(,Con.),Step5,:讀入”54”，42 54，往”42”的右子樹走,54 61,故插入為”61”的右節點,黃國瑜、葉乃菁著,75,8-4-3,二元樹排序法(,Binary-tree Sort,),舉例說明:(,Con.),Step6,:讀入”38”，38 42，往”42”的左子樹走,15 38,往”15”的右子樹走,22 38,故插入為”22”的右節點,黃國瑜、葉乃菁著,76,8-4-3,二元樹排序法(,Binary-tree Sort,),舉例說明:(,Con.),Step7,:用二元樹中序走訪的方式，可得排序結果,15,22,38,42,54,61,黃國瑜、葉乃菁著,77,8-4-3,二元樹排序法(,Binary-tree Sort,),穩定性排序,空間複雜度:,O(n),時間複雜度:,O(n*log,2,n),參考程式,黃國瑜、葉乃菁著,78,8-5,外部排序:合併排序法(,Merge Sort),合併排序法,(1),將欲排序的資料分別存在數個檔案大小可載入記憶,體的檔案中,(2)針對各個檔案分別使用”內部排序法”將檔案中的資,料排序好寫回檔案,(3)再對所有已排序好的檔案兩兩合併,(4)直到所有檔案合併成一個檔案後，則資料排序完成。,(參考,P.8-47,圖例),黃國瑜、葉乃菁著,79,8-5,外部排序:合併排序法(,Merge Sort),假設有四個檔案,A、B、C、D，,其內部資料均已排序完成，則檔案合併排序方式如下：,黃國瑜、葉乃菁著,80,8-5,外部排序:合併排序法(,Merge Sort),舉例說明:,(參考圖例),欲排序的資料如下：,黃國瑜、葉乃菁著,81,8-5,外部排序:合併排序法(,Merge Sort),舉例說明:(,Con.),Step1：length=1,兩兩合併 8,7 、6,5、4,3、2,1,黃國瑜、葉乃菁著,82,8-5,外部排序:合併排序法(,Merge Sort),舉例說明:(,Con.),Step2：length=2,兩兩合併 (7.8),(5.6)、(3.4),(1.2),黃國瑜、葉乃菁著,83,8-5,外部排序:合併排序法(,Merge Sort),舉例說明:(,Con.),Step3：length=4,兩兩合併 (5.6.7.8),(1.2.3.4),黃國瑜、葉乃菁著,84,8-5,外部排序:合併排序法(,Merge Sort),穩定性排序,空間複雜度:,O(n),時間複雜度:,O(n*log,2,n),參考程式,黃國瑜、葉乃菁著,85,8-6,排序法的效率比較,黃國瑜、葉乃菁著,86,