1、排 序 6NCKUEE S.C.Tai NCKUEE Data Compression&Multimedia Communication Lab.1/2/20231排序 把一堆資料或者記錄根據某一個鍵值由小到大或由大而小來排列 內部排序 n在主記憶體中將資料依照某一個順序排列 外部排序 n要排序的資料是在檔案中 NCKUEE Data Compression&Multimedia Communication Lab.1/2/20232為什麼要排序？循序搜尋法 n一串未經排列的數列：5,96,21,67,55,87,12,30 n如果我們想找到21的話，我們就得比對3次n如果要找到12的話，就得
2、比對7次n如果是要確定25並不存在於此數列中則要比對9次n將整個數列比對完後的下一次才會發現已經沒有資料可以比對了欲搜尋數字的大小與比對的次數無關 NCKUEE S.C.Tai 1/2/20233為什麼要排序？如果我將整個數列先經過排序數列變成：5,12,21,30,55,67,87,96可以使用二元搜尋搜尋時間由O(n)降低為O(nlogn)NCKUEE S.C.Tai 1/2/20234穩定排序與不穩定排序 假設我們的原始資料中有兩筆或兩筆以上的資料具有相同的鍵值 當我們做完排序後，這兩筆資料仍然保持它們原先的順序而沒有互換時，就稱為穩定(stable)排序反之，則稱為不穩定(unstab
3、le)排序 NCKUEE Data Compression&Multimedia Communication Lab.1/2/20235穩定排序與不穩定排序原 始 資 料 4 5 7 5+排 序 後 4 5 5+7 穩 定 排 序 後 4 5+5 7 不 穩 定 5+表 示 資 料 為5，但 是 位 置 是 排 在 後 面 的5 NCKUEE Data Compression&Multimedia Communication Lab.1/2/20236泡沫法排序法(Bubble Sort)for(i從0到n-2)將第0個元素到第n-i-1個元素兩兩比較 if(前一個元素下一個元素)互相交換位置
4、;/*每執行一輪，最大值會出現在n-i-1中;*/NCKUEE Data Compression&Multimedia Communication Lab.1/2/20237泡沫法排序法原 始 資 料 5 7 4 5+3 第 一 次 掃 描 5 7 4 5+3 5 4 7 5+3 5 4 5+7 3 5 4 5+3 7 第 二 次 掃 描 4 5 5+3 7 4 5 5+3 7 4 5 3 5+7 第 三 次 掃 描 4 5 3 5+7 4 3 5 5+7 第 四 次 掃 描 3 4 5 5+7 結 果 3 4 5 5+7 四次比較 三次比較 二次比較 一次比較 NCKUEE Data Com
5、pression&Multimedia Communication Lab.1/2/20238泡沫法排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(n)O(n2)O(n2)O(1)n2 0 NCKUEE S.C.Tai 1/2/20239插入排序法(Insertion Sort)for(i從1到n-1)每次將datai中的元素當成欲加入的元素;從已排序完的陣列的最後 往前尋找可以加入的地方;將所有元素往後位移一格;/*每次排序好的陣列為data0到datai;*/NCKUEE S.C.Tai 1/2/202310插入排序法原 始 資
6、 料 5 7 4 5+3 第 一 次 排 列 5 7 4 5+3 第 二 次 排 列 5 7 4 5+3 第 三 次 排 列 5 4 7 5+3 4 5 7 5+3 第 四 次 排 列 4 5 5+7 3 第 五 次 排 列 4 5 5+3 7 4 5 3 5+7 4 3 5 5+7 3 4 5 5+7 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202311插入排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(n)O(n2)O(n2)O(1)n20 NCKUEE
7、S.C.Tai 1/2/202312選擇排序法(Selection Sort)/*在data0datai中的數中，將最大的數放到datai中*/for(i從n-1到1)最大值=data0;for(j從1到i)if(dataj最大值)最大值=dataj;將dataj與datai的資料互換;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202313選擇排序法原 始 資 料 5 7 4 5+3 第 一 次 排 列 3 7 4 5+5 第 二 次 排 列 3 4 7 5+5 第 三 次 排 列 3 4 5+7 5 第 四 次 排 列
8、3 4 5+5 7 NCKUEE S.C.Tai 1/2/202314選擇排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 不 穩 定 O(n2)O(n2)O(n2)O(1)n20 NCKUEE S.C.Tai 1/2/202315快速排序法(Quick Sort)如果n=1，則return；令分隔點K為第一筆資料的值；由左向右找出一筆資料Qi，使得Qi K；由右向左找出一筆資料Qj，使得Qj K；若ij則將Qi與Qj交換，並跳到步驟(2)；若ij則將K與Qj交換，並以j為基點將資料分割成左右兩半，然後分別針對左右兩半進行前面五個步驟 NCKUE
9、E Data Compression&Multimedia Communication Lab.1/2/202316快速排序法Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q1 0 23 7 38 2 69 15 55 20 42 20+K i j 23 7 20+2 69 15 55 20 42 38 i j 23 7 20+2 20 15 55 69 42 38 j i 15 7 20+2 20 23 55 69 42 38 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202317快速排序法Q1 Q2 Q3 Q4
10、 Q5 Q6 Q7 Q8 Q9 Q10 15 7 20+2 20 23 55 69 42 38 Kl i j Kr i j 15 7 2 20+20 23 55 38 42 69 j i j i 2 7 15 20+20 23 42 38 55 69 K,j i K,j i K i,j K,i,j 2 7 15 20+20 23 38 42 55 69 K,j i 2 7 15 20+20 23 38 42 55 69 完成 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202318例子6 2 8 5 11 10 4 1 9
11、7 3使用 6 當分隔點28511104 1973 6針對左右兩半進行排序NCKUEE Data Compression&Multimedia Communication Lab.1/2/202319分隔點之選擇*最左元素隨機選擇前三個元素之中間值NCKUEE Data Compression&Multimedia Communication Lab.1/2/202320例子6 2 8 5 11 10 4 1 9 7 3ab28511104 1973 6左右兩份資料再遞迴地排序NCKUEE Data Compression&Multimedia Communication Lab.1/2/20
12、2321例子 另一種分割法6 2 8 5 11 10 4 1 9 7 3a6836 2 3 5 11 10 4 1 9 7 8a61116 2 3 5 1 10 4 11 9 7 8a610 46 2 3 5 1 4 10 11 9 7 8a6104大的值沒在小值的左邊，停止處理。將分隔值與大值交換。4 2 3 5 1 411 9 7 8a6 106NCKUEE S.C.Tai 1/2/202322分割法-separate x=inputfirst;current_separate=first;for(unknown=first+1;unknown=last;unknown+)if(input
13、unknown x)(current_separate)+;temp=inputcurrent_separate;/*交換current_separate及unknown的位置*/inputcurrent_separate=inputunknown;inputunknown=temp;temp=inputfirst;/*交換first及current_separate的位置*/inputfirst=inputcurrent_separate;inputcurrent_separate=temp;*separate_point=current_separate;NCKUEE S.C.Tai 1/
14、2/202323快速排序法-qsort(int input,int first,int last)if(first last)separate(input,first,last,&separate_point);if(separate_point-first last-separate_point)qsort(input,first,separate_point-1);qsort(input,separate_point+1,last);else qsort(input,separate_point+1,last);qsort(input,first,separate_point-1);NCK
15、UEE Data Compression&Multimedia Communication Lab.1/2/202324快速排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 不 穩 定 O(n)O(nlogn)O(n2)O(n)20n NCKUEE S.C.Tai 1/2/202325合併排序法 將已經排序好的兩個數列合併為一個大的排序好的數列 1.將N個長度為1的數列，合併成N/2個長度為2的數列；2.將N/2個長度為2的數列，合併成N/4個長度為4的數列；3.繼續合併數列，直到形成一個長度為N的數列 NCKUEE Data Compressi
16、on&Multimedia Communication Lab.1/2/202326合併兩個已經排序好的數列 A=(2,5,6)B=(1,3,8,9,10)C=()比較 A 與 B 的最小元素並且將比較小的放入C.A=(2,5,6)B=(3,8,9,10)C=(1)NCKUEE Data Compression&Multimedia Communication Lab.1/2/202327合併兩個已經排序好的數列 A=(5,6)B=(3,8,9,10)C=(1,2)A=(5,6)B=(8,9,10)C=(1,2,3)A=(6)B=(8,9,10)C=(1,2,3,5)NCKUEE Data C
17、ompression&Multimedia Communication Lab.1/2/202328合併兩個已經排序好的數列 A=()B=(8,9,10)C=(1,2,3,5,6)當 A 與 B 有一個已經空了，將沒空的一個直接接到C 的後面。NCKUEE Data Compression&Multimedia Communication Lab.1/2/202329合併排序法 8,3,13,6,2,14,5,9,10,1,7,12,48,3,13,6,2,14,59,10,1,7,12,48,3,13,6 2,14,58,3 13,68 313 62,14 52 149,10,17,12,4
18、9,10 19 107,124712NCKUEE Data Compression&Multimedia Communication Lab.1/2/202330合併排序法 3,8 6,133,6,8,138 313 62,142,5,142,3,5,6,8,13,1452 149,101,9,1019 107,124,7,121,4,7,9,10,121,2,3,4,5,6,7,8,9,10,12,13,144712NCKUEE Data Compression&Multimedia Communication Lab.1/2/202331合併排序法 23 5 25 4 3 5+29 1 3
19、0 17 5 23 4 25 3 5+1 29 17 30 4 5 23 25 1 3 5+29 17 30 1 3 4 5 5+23 25 29 17 30 1 3 4 5 5+17 23 25 29 30 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202332合併排序法void merge(int data,int workspace,int front,int mid,int rear)int input=front;int input1=mid+1;int output=front;while(input=mid&
20、input1=rear)/*將兩序列中較小的放入暫存中*/if(datainput=datainput1)workspaceoutput+=datainput+;else workspaceoutput+=datainput1+;while(input=mid)/*將未比對完的放入暫存中*/workspaceoutput+=datainput+;while(input1=rear)workspaceoutput+=datainput1+;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202333合併排序法 void merge
21、sort(int data,int workspace,int front,int rear)int mid,i;if(front rear)mid=(front+rear)/2;/*將資料分為兩段*/mergesort(data,workspace,front,mid);/*排序左半段 */mergesort(data,workspace,mid+1,rear);/*排序右半段 */merge(data,workspace,front,mid,rear);/*將資料合在一起*/for(i=front;i=rear;i+)datai=workspacei;/*把暫存資料搬回原來的的陣列*/NC
22、KUEE S.C.Tai 1/2/202334合併排序法 穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(nlogn)O(nlogn)O(nlogn)O(n)20n NCKUEE S.C.Tai 1/2/202335堆積排序法(Heap Sort)假設現在我有10筆資料10,66,30,52,61,21,3,27,55,10+組成最小堆積樹 1.先將其放入二元樹中 2.然後調整成為最小堆積樹3.重複地”從樹的頂端彈出最小的元素，以及重新調整剩下的二元樹使其再度成為最小堆積樹”這兩個步驟，NCKUEE Data Compression&Mu
23、ltimedia Communication Lab.1/2/202336堆積排序法先將其放入二元樹中 1052306632161552710+NCKUEE S.C.Tai 1/2/202337堆積排序法然後調整成為如下的最小堆積樹 調整堆積樹的方法請閱讀第五章 3271010+302161555266NCKUEE S.C.Tai 1/2/202338堆積排序法從樹的頂端彈出最小的元素，以及重新調整剩下的二元樹使其再度成為最小堆積樹 10+5210273021615566彈出3之後之最小堆積樹。已排序好之數列=3.1052212730556166彈出10+之後之最小堆積樹。已排序好之數列=3,
24、10+.NCKUEE Data Compression&Multimedia Communication Lab.1/2/202339堆積排序法21523027665561彈出10之後之最小堆積樹。已排序好之數列=3,10+,10.NCKUEE S.C.Tai 1/2/202340堆積排序法void adjust(int x,int root,int item,int boundary)/*修正heap*/int father,son;int done;father=root;/*父節點的位置*/son=2*father;/*子節點的位置*/done=FALSE;while(son=bound
25、ary&!done)/*是否有子節點*/if(sonxson)/*大的節點用來調整*/son+;if(item=1;i-)/*將資料從中間開始加入，並調整heap*/adjust(x,i,xi,n);for(index=n;index=2;index-)/*一個一個移除heap中的元素，*/temp=x1;/*將最大的元素放到陣列最後 */adjust(x,1,xindex,index-1);xindex=temp;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202342堆積排序法穩 定 度 最 佳 狀 況 平 均 狀 況
26、最 差 狀 況 額 外 空 間 使 用 時 機 不 穩 定 O(nlogn)O(nlogn)O(nlogn)O(n)20n NCKUEE S.C.Tai 1/2/202343基數排序法(Radix Sort)多鍵值排序法Key花色：Key點數：A K Q J 10 9 8 7 6 5 4 3 2 2,A,2,A NCKUEE S.C.Tai NCKUEE Data Compression&Multimedia Communication Lab.1/2/202344基數排序法 MSD優先優先 1.分配將含有相同鍵值的資料置於同一箱中；2.排序將各個箱子中的資料分別排序；3.合併將各箱中的資料用
27、插入排序法合成一串 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202345基數排序法-MSD優先優先 80,44,324,44+,3,94,221,8,25,210做排序 步驟步驟1：最高位數為百位數，用百位數當鍵值，將數字分別放在不同的箱子中 0 80 44 44+3 94 8 25 1 2 221 210 3 324 4 5 6 7 8 9 NCKUEE S.C.Tai 1/2/202346基數排序法-MSD優先優先 步驟步驟2：分別將各箱子裡的數值做排序 0 3 8 25 44 44+80 94 2 210 221
28、3 324 NCKUEE S.C.Tai 1/2/202347基數排序法-MSD優先優先 步驟步驟3：合併各箱子裡的資料成一份 3,8,25,44,44+,80,94,210,221,324 NCKUEE S.C.Tai 1/2/202348基數排序法-LSD優先優先 分配從最右邊的位數開始比較，將含有相同鍵值的資料置於同一箱中 重複以上動作，直到到達最大的數的最高位數為止，若最大的數是P位數，則需比較P次 合併將各箱中的資料用插入排序合成一串 NCKUEE S.C.Tai 1/2/202349基數排序法-LSD優先優先 80,44,324,44+,3,94,221,8,25,210 步驟步驟
29、1：步驟1-1：以個位數做比較分配 0 80 210 1 221 2 3 3 4 44 324 44+94 5 25 6 7 8 8 9 NCKUEE S.C.Tai 1/2/202350基數排序法-LSD優先優先 步驟1-2：以十位數做比較分配 0 3 8 1 210 2 221 324 25 3 4 44 44+5 6 7 8 80 9 94 NCKUEE S.C.Tai 1/2/202351基數排序法-LSD優先優先步驟1-3：以百位數做比較分配 0 3 8 25 44 44+80 94 1 2 210 221 3 324 4 5 6 7 8 9 NCKUEE S.C.Tai 1/2/2
30、02352基數排序法-LSD優先優先合併各箱子裡的資料成一份 3,8,25,44,44+,80,94,210,221,324 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202353基數排序法-LSD優先優先/*最無效優先法的基數排序*/void radixsort(int data,int n)index i;建立暫存鍵結串列的結構;/*資料中，最大的數為幾位數就要做幾次排序*/for(i從1到最高位數為止)每次依照第i位分類，若資料的第i位為k就放入第k個暫存鍵結串列中;依鍵值將各個暫存鍵結串列中的資料由小到大放入陣列中
31、;NCKUEE Data Compression&Multimedia Communication Lab.1/2/202354基數排序法穩 定 度 最 佳 狀 況 平 均 狀 況 最 差 狀 況 額 外 空 間 使 用 時 機 穩 定 O(nlogn)O(nlogn)O(n2)O(n)20n NCKUEE Data Compression&Multimedia Communication Lab.1/2/202355外部排序法 當資料量太大時，我們無法將其一次全部放在主記憶體中做處理 因此需要對外部儲存裝置中的資料做排序 外部排序最常用的方法是合併排序法 先將檔案分段 每一段檔案用內部排序法
32、加以排序之後再將它們寫出到外部儲存裝置 NCKUEE S.C.Tai 1/2/202356外部排序法 排序過後的各段資料稱為行程（runs）將各行程利用合併排序法逐漸合併 直到最後只剩下一個行程為止 如果我們使用二路合併，以m個行程來說，需要log2m處理次，如果採用k路合併，則需要logkm次當然，k越大，需要的處理次數就越少NCKUEE S.C.Tai 1/2/202357外部排序法 但是由於每處理一個行程就得寫入記憶體及寫出到外部儲存裝置一次所以當k的數目太大時，反而會讓系統的整體表現變差 NCKUEE Data Compression&Multimedia Communication Lab.1/2/202358外部排序法 R1R2R3R4R5R1_R2R3_R4R1_R2_R3_R4R1_R2_R3_R4_R5二 路合併NCKUEE S.C.Tai NCKUEE Data Compression&Multimedia Communication Lab.1/2/202359
