第十章 排序與搜尋

目次 10.1 排序 10.2 搜尋 10.3 雜湊法 10.4 Trie 10.5 八字形的樹 10.6 動動腦時間 10.7 練習題解答

10.1 排序 排序(sorting) 排序的方法 將一堆雜亂無章的資料由小至大(Ascending)或由大至小(decending)排列之 10.1 排序 排序(sorting) 將一堆雜亂無章的資料由小至大(Ascending)或由大至小(decending)排列之 排序的方法 內部排序(internal sort)：記錄是在主記憶體(main memory)中進行分類 外部排序(external sort)：借助輔助記憶體，如磁碟或磁帶來進行分類

10.1 排序 (con.t) 另外的排序方式 穩定性(stable) 不穩定性(unstable) 比較排序(comparative sort)：排序方式是比較整個鍵值 分配排序(distributive sort)：一次只比較鍵值的某一位數 穩定性(stable) 對於兩個相等鍵值k(i) = k(j)的記錄r(i)和r(j)，如果在原始檔案中，r(i)排在r(j)之前；而在排序後，檔案中的r(i)仍在r(j)之前 不穩定性(unstable) r(j)在r(i)之前

10.1 排序 (con.t) 10.1.1 氣泡排序 氣泡排序(bubble sort) 氣泡排序的特性 10.1.1 氣泡排序 氣泡排序(bubble sort) 又稱交換排序(interchange sort) 相鄰兩個相比，假使前一個比後一個大時，則互相對調 通常有 n 個資料時最多需要做 n–1 次掃瞄，一次掃瞄完後，資料量減少1，當沒有對調時，就表示已排序好了 氣泡排序的特性 氣泡排序是stable 最壞時間與平均時間複雜度均為O(n2)，所需要額外空間也很少

10.1 排序 (con.t) 5個資料，分別是18, 2, 20, 34, 12 氣泡排序的步驟如下： 第一次掃瞄 18 2 20 34 結果 換 4次比較 有二次交換 換

10.1 排序 (con.t) 第二次掃瞄 2 18 20 12 結果 3次比較 換 第三次掃瞄 2 18 12 結果 2次比較 換 第四次掃瞄 2 12 結果 換 1次比較

10.1 排序 (con.t) 10.1.2 選擇排序 選擇排序(selection sort) 10.1.2 選擇排序 選擇排序(selection sort) 首先在所有的資料中挑選一個最小的鍵值，將其放置在第一個位置(因為由小到大排序) 之後，再從第二個開始挑選一個最小的鍵值放置於第二個位置一直下去 假設有n個記錄，則最多需要n–1次對調，以及n(n–1)/2次比較

10.1 排序 (con.t) 選擇排序跟氣泡排序一樣是穩定性的， 最壞時間與平均時間複雜度都是O(n2)，所需要的額外空間亦很少 [1] [2] [3] [4] [5] 18 2 20 34 12 Step 1: 最小為 2 Step 2: 從第2位置開始挑最小為 12 Step 3: 從第3位置開始挑最小為 18 Step 4: 從第4位置開始挑最小為 20

10.1 排序 (con.t) 10.1.3 插入排序 插入排序(insertion sort) 將加入的資料置於適當的位置，如下圖所示： 10.1.3 插入排序 插入排序(insertion sort) 將加入的資料置於適當的位置，如下圖所示： 插入排序是stable，最壞時間與平均時間複雜度為O(n2)，所需額外空間很少 j X0 X1 X2 X3 X4 X5 2 45 39 12 25 30 3 4 5 -∞

10.1 排序 (con.t) 10.1.4 合併排序 合併排序(merge sort) 10.1.4 合併排序 合併排序(merge sort) 將兩個或兩個以上已排序好的檔案，合併成一個大的已排序好的檔案 有兩個檔案分別為甲={2, 10, 12, 18, 25}，乙= {6, 16, 20, 32, 34}；合併排序過程如下： 甲的第一個資料是2，而乙的第一個資料是6，由於2小於6，故將2寫入丙的第一個資料； 甲的第二個資料是10，10比6大，故6寫入丙的第二個資料； 乙的第二個資料為16，16比10大，故10寫入丙的第三個資料； 以此類推，最後丙檔案為{2, 6, 10, 12, 16, 18, 20, 25, 32, 34}

10.1 排序 (con.t) 10.1.5 快速排序 快速排序(quick sort) 10.1.5 快速排序 快速排序(quick sort) 又稱為劃分交換排序(partition exchange sorting) 平均時間而言，快速排序是所有排序中效率不錯的方法 假設有 n 個資料 R1, R2, R3, …, Rn，其鍵值為 K1, K2, K3, …, Kn。快速排序法其步驟如下： 以第一個記錄的鍵值 k1 做基準 K 由左至右 i = 2, 3, …, n，一直找到ki≧K。 由右至左 j = n, n–1, n–2, …, 2，一直找到kj≦K。 當i < j時，Ri 與 Rj 互換，否則 R1 與 Rj 互換

10.1 排序 (con.t) 10.1.5 堆積排序 堆積的特性 堆積排序 父節點皆大於其子節點，而不必管左子節點和右子節點之間的大小 10.1.5 堆積排序 堆積的特性 父節點皆大於其子節點，而不必管左子節點和右子節點之間的大小 堆積排序 unstable，平均時間與最壞時間複雜度是O(nlog2n)，所需的額外空間很少

10.1 排序 (con.t) 假設有一棵二元樹如下： 現在我們要將此十個資料利用堆積排序由大至小排序之 7 27 5 80 24 58 25 67 18 62 2 4 8 1 3 6 9 10

10.1 排序 (con.t) 首先，先將二元樹轉換成heap，如下所示： 第1個節點資料80最大，此時80與第10個(最後一個)的鍵值資料 7 對調，對調之後，最後一個資料就固定不動，下面調整時資料量已減少1個 1 80 67 58 62 5 24 7 25 18 27 2 4 8 3 6 9 10

10.1 排序 (con.t) 因此i=1時，原先堆積變成 67與7對調… 7 67 58 62 5 24 80 25 18 27 1 2 3 6 9 10 67與7對調…

10.1 排序 (con.t) 此時左、右子節點各為67和62，根據heap由上而下的方法調整之，由於67大於62，因此將67與父節點7對調，以同樣的方法只要調整左半部即可(因為67在父節點的左邊)，而右半部不必做調整（因為右半段沒更動），此時並輸出 80 2 3 67 7 58 62 5 24 80 25 18 27 1 2 4 8 3 6 9 調整左半部… 輸出80

10.1 排序 (con.t) [i = 2]：承i=1，先將樹根節點與A[9]對調，其情形如下： 62與7對調， 然後調整右半部… 58 24 62 5 67 80 25 18 27 1 2 4 8 3 6 62與7對調， 然後調整右半部… 輸出67

10.1 排序 (con.t) [i = 3]：承i=2，先將樹根節點與A[8]對調，其情形如下： 以此類推，最後的輸出結果為 80，67，62，58，27，25，24，18，7，5 5 58 24 27 62 67 80 25 7 18 58與5對調， 然後調整左半 部… 輸出62

10.1 排序 (con.t) 10.1.7 謝耳排序 謝耳排序(shell sort)方法如下： 10.1.7 謝耳排序 謝耳排序(shell sort)方法如下： 假設有9個資料，分別是39, 11, 48, 5, 77, 18, 70, 25, 55 先將所有的資料分成 Y = (9/2)部份，即Y = 4，Y為劃分數，其中第1, 5, 9個數字是第一部份；第2, 6個數字是屬於第二部份；第3, 7個數字是第三部份；第4, 8個數字是第四部份。 每一循環的劃分數是Y，皆是上一循環二分數除以2，即Yi+1 = Yi/2，最後一個循環的劃分數為1 先比較每一部份的前兩個，如[1:5]，[2:6]，[3:7]，[4:8]，及[5:9] 前兩個比較完成後，再比較每一部份的第二個和第三個，將較小的放入第二個，放入後還要和第一個相比較，若比第一個小，則需要調換。

10.1 排序 (con.t) 10.1.8 二元樹排序 二元樹排序(binary tree sort) 10.1.8 二元樹排序 二元樹排序(binary tree sort) 是先將所有的資料建立成二元搜尋樹，再利用中序法來追蹤，步驟如下： 將第一個資料放在樹根。 進來的資料皆與樹根相比較，若比樹根大，則置於右子樹；反之，置於左子樹。 二元搜尋樹建立完後，利用中序法追蹤，即可得到由小至大的排序資料

10.1 排序 (con.t) 10.1.9 基數排序 基數排序(radix sort) 10.1.9 基數排序 基數排序(radix sort) 又稱為bucket sort或bin sort，它是屬於distribution sort 基數排序是依據每個記錄的鍵值劃分為若干單元，把相同的單元放置在同一箱子 排序的過程可採用LSD(Least Significant Digital)或MSD(Most Significant Digit) 基數排序是 stable，所需的平均時間複雜度是 O (n logr m)，其中 r 為所採用的數字系統的基底，m 為堆數。在某些情況下所需時間是O(n)，所需空間很大，需要(n*n)，n為記錄數

10.2 搜尋 搜尋的方式 搜尋技巧 內部搜尋：直接存放在主記憶體找尋 外部搜尋：藉助輔助記憶體才能找尋時 10.2 搜尋 搜尋的方式 內部搜尋：直接存放在主記憶體找尋 外部搜尋：藉助輔助記憶體才能找尋時 搜尋技巧 順序搜尋(sequential search) 二元搜尋(binary search) 插補法搜尋(interpolation search) 雜湊函數(Hashing function)

10.2 搜尋 (con.t) 10.2.1 順序搜尋 順序搜尋 又稱為線性搜尋(linear search)，它適用於小檔案。這是一種最簡單的搜尋方法，從頭開始找，一直到找到或檔案結束（表示找不到）為止 順序搜尋的Big-O為O(n)

10.2 搜尋 (con.t) 10.2.2 二元搜尋 二元搜尋 從一個已排序的檔案中找尋資料 二元搜尋的觀念與二元搜尋樹十分類似 10.2.2 二元搜尋 二元搜尋 從一個已排序的檔案中找尋資料 二元搜尋的觀念與二元搜尋樹十分類似 其比較是從所有記錄的中間 M 開始，若欲搜尋的鍵值小於 M，則從 M 之前的記錄繼續搜尋，否則搜尋 M 以後的記錄，如此反覆進行，直到要找尋資料的鍵值被找到為止

10.2 搜尋 (con.t) 10.2.3 插補法搜尋 插補法搜尋(interpolation) 10.2.3 插補法搜尋 插補法搜尋(interpolation) 適合用於當鍵值分佈呈現均勻分佈(uniform distribution)時 例如：當我們查字典欲找尋BRIGHT時，我們大致會先翻到B字母開頭的地方，然後再往前翻或往後翻慢慢修正，直到找到為止 插補法搜尋公式 得知與第幾筆記錄比較，公式中s[]為一陣列，存放已被排序好的資料，low與upper分別為陣列的開頭與結尾的位置，x為欲搜尋的鍵值，而n為資料的個數

10.2 搜尋 (con.t) 10.2.4 字串搜尋 字串搜尋方法 暴力法(brute force) KMP字串搜尋法 10.2.4 字串搜尋 字串搜尋方法 暴力法(brute force) 最簡單的字串搜尋方法，但是搜尋的效率卻也是最差的 將字串中的字元逐一比對，直到找到合乎的字串為止 KMP字串搜尋法 最常被使用的方式

10.3 雜湊法 雜湊法(Hashing) 鍵值(key value)或識別字(identifier)在記憶體的位址是經由函數(function)轉換而得的 此種函數，一般稱之為雜湊函數(Hashing function)或鍵值對應位址轉換(key to address transformation) 適用於有限的儲存空間，並能夠有效使用且在加入或刪除時也能快速的完成 雜湊表搜尋在沒有碰撞(collision)及溢位(overflow)的情況下，只要一次就可擷取到 h(k) r:index k:key

10.3 雜湊法 (con.t) 10.3.1 雜湊函數 常用的雜湊函數有下列三種方法： 平方後取中間值法(mid-square) 10.3.1 雜湊函數 常用的雜湊函數有下列三種方法： 平方後取中間值法(mid-square) 此種方法乃是先將鍵值平方，然後視儲存空間的大小來決定取幾位數。 例如，有一鍵值是510324，而其儲存空間為1000；將510324平方後，其值為260430584976，假設由左往右算起取其第六位至第八位，此時058就是510324所儲存的位址。 除法(division) 此種方法將鍵值利用模數運算(mod)後，其餘數即為此鍵值所對稱的位址，亦即Fd(x) = x mod m，由此式得到位址的範圍是0至(m–1)之間。而m值的最佳選擇是：只要m值為不小於20的質數就可以。 數位分析法(digit analysis) 此種方法適合大的靜態資料，亦即所有的鍵值均事先知道，然後檢查鍵值的所有位數，分析每一位數是否分佈均勻，將不均勻的位數刪除，然後根據儲存空間的大小來決定位數的數目

10.3 雜湊法 (con.t) 10.3.2 解決溢位的方法 當溢位(overflow)發生時應如何處理？ 10.3.2 解決溢位的方法 當溢位(overflow)發生時應如何處理？ 線性探測(linear probling)：是把雜湊位址視為環狀的空間，當溢位發生時，以線性方式從下一號桶開始探測，找尋一個空的儲存位址將資料存入。若找完一個循環還沒有找到空間，則表示位置已滿 重覆雜湊(rehashing)：乃是先設計好一套的雜湊函數f1，f2，f3，…，fm，當溢位發生時先使用f1，若再發生溢位則使用f2……，一直到沒有溢位發生

10.3 雜湊法 (con.t) 平方探測(quadratic probing)：此法是用來改善線性探測之缺失，避免相近的鍵值聚集在一塊。當f(x)的位址發生溢位時，下一次是探測(f(x) + i2) mod b，及(f(x) + i2) mod b其中1≦i≦(b-1)/2，b是具有4j+3型式的質數。 鏈結串列(chaining)：是將雜湊空間建立成b個串列，起初只有b個串列首，故放起始位址，並不存放資料，相同位址的鍵值，將形成一個鏈結串列

10.4 Trie Trie 索引(index)的結構，它用於當鍵值是不一樣長度時 此一結構中包含兩種節點的型態， 元素節點(element node)：資料內容 分支節點(branch node)：指向子樹(subtrees)的指標

10.4 Trie (con.t) 假設有small, smart, zoo, goat, golf, gulf, bright, penguin, park，其Trie的結構如下： a b c d g p s z … … … zoo … m l a r small smart e park penguin u goat golf o gulf bright

10.4 Trie (con.t) 加入一鍵值到Trie 當加入brisk時，b之下的結構則改變為 a b c d g p s z … a b c d g p s z … … … r o u a e m … zoo i a l a gulf penguin g s goat golf l r park … bright brisk small smart

10.4 Trie (con.t) 當從Trie刪除某一鍵值 當刪除brush時，則只要直接刪除即可，此時Trie並不會被更動到，如下圖所示： a b c d g p s z … … … r o u a e m … zoo i o u a l a gulf penguin g s browser goat l r golf park … brush bright brisk small smart

10.4 Trie (con.t) 當再刪除brisk時，則此時的Trie就會被更動到，如下圖所示： a b c d g p s z … a b c d g p s z … … … r o u a e m … zoo i o a l a gulf penguin bright browser goat l r golf park … small smart

10.5 八字型的樹 八字型的樹(Splay tree) 為何要有八字型的樹？ 10.5 八字型的樹 八字型的樹(Splay tree) 是一棵二元搜尋樹，其加入、刪除、搜尋方式皆與一般的二元搜尋樹相同 為何要有八字型的樹？ 當一棵二元搜尋樹呈現狹長型時，若經過調整而變成「矮胖型」，則這種形態的二元搜尋樹就稱為「八字型的樹」，其作用在於可增加二元搜尋樹搜尋的效率

10.5 八字型的樹 (con.t) 八字型的樹的調整方式 RR型 與AVL-tree的調整方式是相當類似的，但仍有不同處 分有RR型、LL型、RL型、LR型，調整時是從最下面的node先開始 RR型 b d c gp a p g c a b g 1 d p gp 經調整後 　

10.5 八字型的樹 (con.t) LL型 RL型 經調整後  經調整後  d a b g c p gp b c d gp a p g gp a p g 經調整後  d b c gp p a g 經調整後 　

10.5 八字型的樹 (con.t) LR型 d c b p a g gp gp d c a g b p 經調整後 　　