资料结构与演算法

《资料结构与演算法》由会员分享，可在线阅读，更多相关《资料结构与演算法（36页珍藏版）》请在金锄头文库上搜索。

1、第七章 排序,資料結構與演算法,徐熊健,7.1 排序的考量7.2 排序演算法7.3 排序究竟可以有多快,目錄,排序 (sorting) 是個既重要又經常用到的運算。舉凡資料的整理、搜索，都有排序資料的需求； 對排序過的資料運用二元搜尋演算法進行搜索，往往是各類搜索問題的核心技術；各種商用的資料庫，也以排序和搜尋的速度相互較量； 許多組合問題 (combinatorial problem) 的解決，都以排序為其前置運算 (pre-processing)，例如在加權圖形中找最小延展樹的Kruskal演算法，就得先對所有的邊，依其距離做由小至大的排序處理。,第七章 排序,排序的目的是將相同性質的資料

2、，依其順序關係（由小至大或由大至小）排列；隊伍中的身高關係、英文字典中的字詞順序、公司薪資的高低、事件發生具今的遠近、，都是可以排序的資料。 在關聯式資料庫 (relational database) 的記錄 (record) 中，每個欄位也都可能是排序的對象； 一般而言主欄位 (key field)大都會加以排序，以方便使用者觀察或取用所要的記錄資料。當資料涉及資料庫時，我們皆以主鍵欄代表整筆紀錄。,7.1 排序的考量,依據排序資料存放位置的不同，排序的範疇可分成兩種： (1)內部排序法 (internal sorting) ：指的是資料全部在主記憶體中。 (2)外部排序法 (externa

3、l sorting) ；指的是主記憶體中只存放部分資料，而大部分的資料皆在外部記憶體 (如，硬碟、磁帶檔案) 中。,7.1 排序的考量,兩種排序方式在存取速度方面，有顯著的差異： 內部排序法的資料存取皆在主記憶體中進行，而主記憶體屬於隨機存取設備 (random access device) ，遂速度較快。 而外部排序法的資料大多在硬碟、磁帶等循序存取設備 (sequential access device) 中，所以存取速度會慢上許多，處理資料的量通常也比內部者大上許多。 本章的討論以內部排序法為主。,7.1 排序的考量,7.2.1 挑選排序法 7.2.2 插入排列法 7.2.3 氣泡排序法

4、 7.2.4 Shell排序法 7.2.5 合併排序法 7.2.6 快速排序法 7.2.7 基數排序法 7.2.8 堆積排序法,7.2 排序演算法,欲排序的n筆資料先行存放在一維陣列中，利用n次迴圈完成排序在第i次迴圈時，挑出第i小的資料將之與陣列中第i筆資料對調即可重整陣列使成為由小至大排序的數列。在2.2.1節中也提及其時間複雜度為O(n2)。 挑選演算法除了幾個局部變數 (local variable) 外，並不需額外的空間。某個資料在找比它小的資料時，會有資料對調的動作；這個動作可能使得值相同值的資料，不再保持原來的相對先後順序，遂排選排序法不具穩定性。,7.2.1 挑選排序法,插入排

5、序法 (insertion sort) 是將排序的過程視為：將未排序的資料遂一插入已排序的部分資料中。下圖7-1顯示了第i筆資料插入前i-1筆已排序資料的動作：,7.2.2 插入排列法,演算法7-1插入排序法 輸入：整數陣列data，長度為n 輸出：排序陣列data，若itarget) 9 ,7.2.2 插入排列法,7.2.3 氣泡排序法,當資料希望以小至大（由上而下）排序時，氣泡排序法 (bubble sort) 要求相鄰的兩元素要維持上小下大的順序關係； 相鄰的兩元素會互相比較大小，將較大的資料往下放。 一旦大資料被放到最下面，他應比其它所有資料都大，他肯定是最大的資料；於是同法找出次大、

6、第三大、；即可完成排序的動作。 氣泡之名實來自其大資料向下沉去、或小資料向上浮出，好似重物投入水中下沉，而其擠壓之氣泡往上竄出之現象。,演算法7-2氣泡排序法 輸入:整數陣列data，共計n筆資料 輸出:排序陣列data，若i0; i-) 2 for (j=1; jdataj) 4 swap(dataj-1, dataj);,7.2.3 氣泡排序法,Shell排序法是由Donald Shell所提出的，由上一節氣泡排序法的經驗可知：即令原來的資料尚未完全排序完成，但若有不少資料已位在它們在排序完成時應處的位置上，則可減少資料搬移的動作。 直覺來想：資料的大小順序符合者愈多，可減少資料交換的個數

7、，對所有資料的排序愈有利。 Shell排序法的概念即希望以分組排序、逐次增加大小順序符合的資料個數來進行排序：資料先行分成小組，各小組進行排序，由於各組內的資料已依大小順序排放，則整體再併成大組排序時，應可獲得減少資料交換的好處。,7.2.4 Shell排序法,演算法7-3 Shell排序 輸入：整數陣列data，共計n筆資料；ht, ht-1, ., h1，且h1=1 輸出：排序陣列data，若itarget) 11 12 ,7.2.4 Shell排序法,在實際應用上Shell排序是不錯的排序選擇。它不需額外的記憶空間； 不過它不具穩定性，理由是分組個別排序時，值相同的資料可能不在同一組，相

8、對先後順序可能因而不再保持。,7.2.4 Shell排序法,合併排序 (merge sort) 的概念則是將兩組已各自排序好的數列予以合併，使成為一完整的排列數列。 令陣列A存放了m個已排序的資料，陣列B存放了n個已排序的資料，合併排序的目的即希望將陣列A和B各別已排序的資料，合併存放至陣列C中，即C會共存m+n筆已排序的資料。,7.2.5 合併排序法,演算法7-4 合併兩個已排序的數列 輸入：已排序陣列A，共m筆資料；已排序陣列B，共n筆資料 輸出：排序陣列C，若ij，則CiCj，0i,jm+n-1 1 void merge(int C, int k, int A, int i, int m

9、, int B, int j, int n) 2 while (i=m) 10 ,7.2.5 合併排序法,演算法7-5合併排序（遞迴版） 輸入：data陣列共計n筆資料 輸出：排序陣列data，若ij則dataidataj，0i,jn-1 1 int k=0; datan; 2 void merge_sort(int A, int left, int right) 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 mer

10、ge(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 ,7.2.5 合併排序法,演算法7-6合併排序（非遞迴版） 輸入：data陣列共計n筆資料 輸出：排序陣列data，若ij，則dataidataj，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)

11、; 6 len *= 2; 7 8 ,7.2.5 合併排序法,在合併排序中，我們已引用了分割和個自擊破的演算法策略先分割、個自擊破，爾後再不斷地合併出最後的結果。 試想：倘若不必合併是否可以得到節省時間的好處？ 若分割出的兩個子數列其一中的所有值，完全比另一中的所有值要小（稱前者為小子數列、後者為大子數列），則兩個子數列即可各自排序，不必合併，直接把排序後的大子數列，接在排序後的小子數列之後，即得整個數列的排序結果！ 這就是C. A. R. Hoare所提出快速排序法 (quicksort) 的概念。,7.2.6 快速排序法,細部設計如下：首先選取某個元素做為基準值（通常選第一個元素data0

12、），令此基準值為target， 然後將所有比target小的資料，都放在target的左邊； 而所有不比target小的資料都放在target的右邊。,7.2.6 快速排序法,演算法7-7：遞迴快速排序 輸入：整數陣列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 = da

13、taleft; 7 do 8 while (dataitarget 15 16 ,7.2.6 快速排序法,演算法7-8堆疊和迴圈實作快速排序 輸入：整數陣列data,共n筆資料(data0datan-1),datan=MaxInt 輸出：排序陣列data，若ij，則dataidataj，0i,jn-1 1 left = 0; 2 right = n-1; 3 push(left, right); 4 while (堆疊中仍有元素) 5 (left, right) = pop(); 6 target = dataleft; 7 i = left+1; 8 j = right; 9 do 10 w

14、hile (dataitarget 17 18 ,7.2.6 快速排序法,快速排序法的時間複雜度,The best case: L, R 子數列皆等長! T(n) = 2T(n)+cn = O(nlogn) The worst vase Sorted or reversely sorted n+(n-1)+(n-2)+ + 1 = O(n2) The average case O(nlogn),快速排序法在分割出子數列的資料個數少於10個左右時，可直接用挑選或插入排序法，直接排序該子數列（這些排序法在資料個數少時執行速率頗佳）；如此所需堆疊的空間亦可減少（個數少的子數列先行挑選或插入排序，可減

15、少堆疊空間）。 也有學者對target的選用有不同的建議：有人認為用亂數決定target、有人建議在data0、datan/2和datan-1三者之中找出中位數 (median) 做為target、。這些想法無非在儘可能地讓target可將數列分出長短約莫相同的L和R子數列，而使快速排序的時間儘可能地接近O(nlogn)。 快速排序法需要額外的堆疊空間，不具有穩定性（因在交換datai和dataj時，可能破壞值相同資料的相對順序關係）。,7.2.6 快速排序法,基數排序法 (radix sort) 的比較資料大小概念，與之前排序法的概念不太一樣它的大小比較是與輸入數列的基底位數有關。 假設輸入

16、的數字皆為三位數，那麼基數排序法即先對所有資料的百位數進行排序，再對每一組百位數字相同的資料進行十位數字的排序，爾後再針對每一組十位數字相同的資料，進行個位數字的排序。 這個順序由高位數開始排至低位數，稱為高位數優先 (most significant digit first) ； 事實上先排個位數，再排十位數，爾後百位數；一樣可以得到排序的結果，這個順序則為低位數優先 (least significant digit first) 。,7.2.7 基數排序法,演算法7-9基數排序 輸入：整數陣列data,共n筆資料(data0datan-1), 輸出：排序陣列data，若imax) max

17、= 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 = 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 ,