鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第九章：排序與搜尋 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

Presentation on theme: "鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第九章：排序與搜尋 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/"— Presentation transcript:

1 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/
資料結構 第九章：排序與搜尋 鄧姚文

2 排序（Sorting） 內部排序（Internal Sort） 外部排序（External Sort） 將資料全部載入主記憶體，進行排序
資料量非常龐大，無法全部載入主記憶體，須藉助輔助記憶體（硬碟、磁帶）進行排序 2019/1/18

3 排序（Sorting） 比較排序（Comparative Sort） 分配排序（Distributive Sort）
比較整個鍵值（Key Value） 分配排序（Distributive Sort） 一次只比較鍵值的某一位數 2019/1/18

4 排序（Sorting） 穩定性（Stability） 鍵值相同的兩筆記錄R1, R2
若在排序前R1位於R2之前，經過排序之後R1仍位於R2之前，則稱該排序法為具有穩定性（Stable）的排序法；反之則稱之為不穩定（Unstable）的排序法 2019/1/18

5 氣泡排序（Bubble Sort） 交換排序 對N筆資料進行掃瞄，將相鄰的兩筆資料相比，如果前一個比後一個大，則將兩筆資料對調
N筆資料需要N-1次掃瞄 時間複雜度O(N2) Stable Comparative Sort 2019/1/18

6 氣泡排序（Bubble Sort） 18 2 20 34 12 2 18 20 12 34 2 18 12 20 34 2 12 18 20 34 2 12 18 20 34 2019/1/18

7 氣泡排序（Bubble Sort） void bubble_sort(int data[], int size) {
int base, compare, temp; for (base = 0; base < size - 1; base++) { /* 讓資料兩兩比較，將小的置於前 */ for (compare = base + 1; compare < size; compare++) if (data[base] > data[compare]) { temp = data[compare]; data[compare] = data[base]; data[base] = temp; } 2019/1/18

8 氣泡排序（Bubble Sort）JAVA
public BubbleSortDemo(int[] A) { boolean done = false; for (int i = A.length; (i > 0) && (!done); i--) { done = true; for (int j = 0; j < i-1; j++) { if (A[j] > A[j+1]) { int t = A[j]; A[j] = A[j+1]; A[j+1] = t; done = false; } 2019/1/18

9 插入排序法（Insertion Sort）
將新的鍵值K插入到一依序排列的串列L之中 比較大小，找尋適當位置，邊找邊搬（挪出空位） 時間複雜度：O(N2) Best Case：若資料原來就已經完成排序，則插入排序法不搬動資料 Stable Comparative Sort 2019/1/18

10 插入排序法（Insertion Sort）
45 39 12 25 30 39 45 12 25 30 12 39 45 25 30 12 25 39 45 30 12 25 30 39 45 2019/1/18

11 插入排序法（Insertion Sort）
void insertion_sort(int data[], int size) { int base, compare, temp; for (base = 1; base < size; base++) /* 當資料小於第一筆，則插於前方，否則與後面資料比對找出插入位置 */ temp = data[base]; compare = base; while (compare > 0 && data[compare - 1] > temp) { data[compare] = data[compare - 1]; compare--; } data[compare] = temp; 2019/1/18

12 謝耳排序（Shell Sort） 插入排序（Insertion Sort）的改良版 搬移的距離：
在插入排序法之中，每次找尋新鍵值的插入位置時，陣列元素持續地被搬移到隔壁的位置 若某一鍵值離其正確位置（最終的位置）很遠，上述之『搬移到隔壁的位置』就會重複很多次 將搬移的距離加大是否會有幫助？ 若資料陣列已經非常接近依序排列的狀態，則插入排序法搬移資料的次數減少 搬移的距離： 第一次：N/2 第二次：N/4 … 最後一次：1 2019/1/18

13 謝耳排序（Shell Sort） 時間複雜度：最壞O(N2)，平均O(N1.5) Unstable Comparative Sort
2019/1/18

14 謝耳排序（Shell Sort） 1 2 3 4 5 6 7 8 9 10 11 12 10 16 11 4 15 3 9 6 1 17 8 12 7 10 16 11 4 15 3 9 6 1 17 8 12 7 13/2=6 7 6 1 4 8 3 9 16 11 17 15 12 10 7 6 1 4 8 3 9 16 11 17 15 12 10 13/4=3 4 6 1 7 8 3 9 15 11 10 16 12 17 4 6 1 7 8 3 9 15 11 10 16 12 17 13/8=1 1 3 4 6 7 8 9 10 11 12 15 16 17 2019/1/18

15 選擇排序（Selection Sort） 第一回：挑選出最小的鍵值放在第一個位置 第二回：挑選出第二小的鍵值放在第二個位置 …
第N-1回：挑選出第N-1小的鍵值放在第N-1個位置 時間複雜度O(N2)，但是實際上搬動資料的次數只有O(N) Stable Comparative Sort 2019/1/18

16 選擇排序（Selection Sort） 18 2 20 34 12 2 18 20 34 12 2 12 20 34 18 2 12 18 34 20 2 12 18 20 34 2019/1/18

17 選擇排序（Selection Sort） void select_sort(int data[], int size) {
int base, compare, min, temp; for (base = 0; base < size - 1; base++) { /* 將目前資料與後面資料中最小的對調 */ min = base; for (compare = base + 1; compare < size; compare++) if (data[compare] < data[min]) min = compare; if (min != base) { temp = data[min]; data[min] = data[base]; data[base] = temp; } 2019/1/18

18 合併排序（Merge Sort） 將兩個各自依序排列的串列L1、L2合併成一個依序排列的串列L 合併排序：
將三個指標p、p1、p2各自指向L、L1、L2的頭端 比較p1所指的鍵值與p2所指的鍵值，將較小的搬到p所指的位置 重複上述兩的動作直到L1與L2都搬完為止 合併排序： 持續將一堆沒有順序的資料分割成兩半，直到每一份都只有一筆資料 將分割完畢的資料兩兩合併 時間複雜度O(N log N)，需要額外的空間 Stable Comparative Sort 適合外部排序 2019/1/18

19 將兩個各自依序排列的串列L1、L2合併成一個依序排列的串列L
10 12 18 25 2 6 10 12 16 18 20 25 32 34 6 16 20 32 34 2019/1/18

20 合併已排序之串列 void merge(int data1[], int data2[], int data3[], int size1, int size2) { int arg1 = 0, arg2 = 0, arg3 = 0; data1[size1] = 32767; data2[size2] = 32767; for (; arg3 < size1 + size2; arg3++) { /* 比較兩數列，資料小的先存於合併後的數列 */ if (data1[arg1] < data2[arg2]) { data3[arg3] = data1[arg1]; arg1++; } else { data3[arg3] = data2[arg2]; arg2++; } 2019/1/18

21 快速排序（Quicksort） Divide-and-Conquer Partition-Exchange 演算法
以第一筆資料的鍵值K1為基準，將N筆資料分為左右兩份，左邊那一份的鍵值都比K1小，右邊那一份的鍵值都大於K1 將左邊那一份與右邊那一份分別以Quicksort排序 時間複雜度：平均O(N log N)，最差O(N2) Unstable Comparative sort 2019/1/18

22 快速排序（Quicksort） 39 11 48 5 77 18 70 25 55 33 18 11 33 5 25 39 70 77 55 48 5 11 18 33 25 39 55 48 70 77 5 11 18 25 33 39 48 55 70 77 2019/1/18

23 void quick_sort(int data[], int left, int right, int size)
{ /* left與right分別表欲排序資料兩端 */ int lbase, rbase, temp; if (left < right) { lbase = left + 1; while (data[lbase] < data[left]) lbase++; rbase = right; while (data[rbase] > data[left]) rbase--; while (lbase < rbase) {/* 若lbase小於rbase，則兩資料對調 */ temp = data[lbase]; data[lbase] = data[rbase]; data[rbase] = temp; lbase++; while (data[lbase] < data[left]) lbase++; rbase--; while (data[rbase] > data[left]) rbase--; } temp = data[left]; data[left] = data[rbase]; quick_sort(data, left, rbase - 1, size); quick_sort(data, rbase + 1, right, size); 2019/1/18

24 堆積排序（Heap Sort） 演算法1： 將N筆資料存入Heap：每一筆資料存入後，Heap花O(log N)重整，共需O(N log N) 自Heap取出N筆資料：每次刪除根節點後重整需要O(log N)，刪除N次共需O(N log N) 合計時間複雜度 O(N log N) 2019/1/18

25 堆積排序（Heap Sort） 已存在一資料陣列，內有N筆資料 演算法2： 將一維陣列轉換成Heap： 做N次資料刪除：O(N log N)
將這N筆資料視為一Complete Binary Tree，如同二元樹之陣列表示法一般 A[i]的左子位於A[2i]，右子位於A[2i+1]，父親位於A[i/2] 從A[N/2]開始依據Heap之規則進行調整（A[N/2]是最後一個Internal Node），接下來調整A[N/2 -1]，…，直到A[1] 時間複雜度O(N) 做N次資料刪除：O(N log N) 2019/1/18

26 將一維陣列轉換成Heap 2019/1/18

27 將一維陣列轉換成Heap #1 2019/1/18

28 將一維陣列轉換成Heap #2 2019/1/18

29 將一維陣列轉換成Heap #3 2019/1/18

30 將一維陣列轉換成Heap #4 2019/1/18

31 將一維陣列轉換成Heap #5 2019/1/18

32 二元樹排序（Binary Tree Sort）
將資料建構成二元搜尋樹（Binary Search Tree） 中序追蹤（In-order Traversal） 2019/1/18

33 基數排序（Radix Sort） 又稱為Bucket Sort或Bin Sort 屬於Distribution Sort Stable
排序過程可自LSD（Least Significant Digit）或MSD（Most Significant Digit）開始 d位數需做d次分配 屬於Distribution Sort Stable 時間複雜度：O(N) 總共搬動資料的次數是d*N，d視為常數 2019/1/18

34 基數排序（Radix Sort）#1 radix=10
199 228 326 118 879 882 076 032 291 056 882,032 326,076,056 228,118 199,879 1 2 3 4 5 6 7 8 9 2019/1/18

35 基數排序（Radix Sort）#2 radix=10
291 882 032 326 076 056 228 118 199 879 118 326,228 032 1 2 3 4 056 076,879 882 291,199 5 6 7 8 9 118 326 228 032 056 076 879 882 291 199 2019/1/18

36 基數排序（Radix Sort）#3 radix=10
118 326 228 032 056 076 879 882 291 199 032,056,076 118,199 228,291 326 1 2 3 4 879,882 5 6 7 8 9 032 056 076 118 199 228 291 326 879 882 2019/1/18

37 Radix Sort 演算法 Algorithm radix_sort(A, first, last, maxDigits)
// Sorts the array of positive decimal integers A[first, last] // into ascending order; // maxDigits is the number of digits in the longest integer for (i = 1 to maxDigits) { Clear bucket[0], bucket[1], ..., bucket[9] for (index = first to last) digit = i-th digit from the right of A[index] Place A[index] at end of bucket[digit] } Place contents of bucket[0], bucket[1], ..., bucket[9] into the array A 2019/1/18

38 各種排序演算法時間複雜度 Average Case Best Case Worst Case Bubble Sort O(N2)
Insertion Sort O(N) Shell Sort O(N1.5) Selection Sort Merge Sort O(N log N) Quicksort Radix Sort Heap Sort 2019/1/18

39 搜尋（Search） 分類：資料是否可以全部載入主記憶體？ 內部搜尋（Internal Search）
外部搜尋（External Search） 2019/1/18

40 Sequential Search 原始資料未排序 Sequential Search 順序搜尋、循序搜尋
又稱為 Linear Search 線性搜尋 時間複雜度：O(N) 改良： 每次搜尋完畢後將搜尋到的目標鍵值移到最前面 計算各項鍵值被搜尋的次數，將資料依照熱門、冷門的順序排列 2019/1/18

41 Sequential Search int sequential_search(int data[], int target, int n) { int i; for (i = 0; i < n; i++) { if (target == data[i]) { return i; } return -1; 2019/1/18

42 Binary Search 原始資料已經完成排序 二元搜尋、二分搜尋
比對搜尋範圍內的中間點，若中間點的鍵值與搜尋目標不符，則比較兩者之大小以判定搜尋目標應落於中間點的左方或右方，進而將搜尋範圍縮小成一半大小，遞迴地進行搜尋 時間複雜度：O(log N) 1 2 3 4 5 6 7 8 9 找 5 大 小 中 2019/1/18

43 Binary Search int binary_search(int data[], int n, int target) {
int left = 0, right = n-1, mid; while (left <= right) { mid = (left + right) / 2; if (target == data[mid]) { return mid; } else if (target > data[mid]) { left = mid + 1; } else { right = mid - 1; } return -1; 2019/1/18

44 Interpolation Search 插補法
鍵值呈均勻分佈（Uniform Distribution） 其中s[]即資料陣列，x為搜尋目標，low相當於二元搜尋法之中的搜尋範圍左邊界（left），high相當於二元搜尋法之中的搜尋範圍右邊界（right） 2019/1/18

45 字串搜尋 Pattern Matching 在一個字串之中找尋相符的特定字或子句 暴力法 Brute Force Method
例如：在下列字串中搜尋 “天才” 這個子句 “交作業的期限早就過了，你怎麼今天才交？” 暴力法 Brute Force Method 依序從字元陣列中的每一個位置開始，逐字比對 時間複雜度：O(NM)，N是被搜尋字串的長度，M是搜尋字串（Pattern）的長度 2019/1/18

46 字串搜尋－暴力法 int strfind(char *string, char *pattern) {
int pos_s, pos_p, len_s, len_p; len_s = strlen(string); len_p = strlen(pattern); /* 字串從string的第一個元素依序比較至元素(len_s-len_p) */ for (pos_s = 0; pos_s <= len_s - len_p; pos_s++) { for (pos_p = 0; pos_p < len_p; pos_p++) { /* 字元比對不正確，則中斷這次的比較 */ if (pattern[pos_p] != string[pos_s + pos_p]) break; /* 若pos_p為pattern的最後一個字元，表示搜尋成功 */ if (pos_p == len_p - 1) return pos_s; } return -1; /* 搜尋失敗 */ 2019/1/18

47 字串搜尋－KMP法 Knuth-Morris-Pratt 要從先前的字串比較之中獲得Pattern的特性 ，依此改善字串搜尋的效率
Failure function 在Pattern內比對相符的前置字串（Prefix）長度 Table of next possible matching positions 2019/1/18

48 字串搜尋－KMP法 2019/1/18

49 Knuth-Morris-Pratt Algorithm
Pre-compute table of next possible matching positions Try to match the characters If there is a mismatch, use the look-up table to find where to start matching next If the relevant part of the table is -1, increment the position on the main string If any other number, begin comparison at this location on the pattern but at the current position on the main string If there is a complete match, you can find the start position by taking the pattern index of the last matched character away from the current position After a complete match, check the last position in the next array: this will tell you if you can attempt another match starting in this string again Return matches 2019/1/18

50 Pre-compute table of next possible matching positions
void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; if (x[i] == x[j]) kmpNext[i] = kmpNext[j]; else kmpNext[i] = j; } x: the search pattern m: length of the search pattern 2019/1/18

51 KMP Pattern Matching void KMP(char *x, int m, char *y, int n) {
int i, j, kmpNext[XSIZE]; /* Preprocessing */ preKmp(x, m, kmpNext); /* Searching */ i = j = 0; while (j < n) { while (i > -1 && x[i] != y[j]) i = kmpNext[i]; i++; j++; if (i >= m) { OUTPUT(j - i); } 2019/1/18

52 雜湊法（Hashing） 理想狀況： 用途 實際情形： O(1) 搜尋 加速搜尋速度 使用較小的陣列處理廣大人口的資料 加密
h(k) k:key r:index Hash function 雜湊函數 鍵值 識別字 索引值 儲存位置 理想狀況： O(1) 搜尋 用途 加速搜尋速度 使用較小的陣列處理廣大人口的資料 加密 實際情形： 碰撞（Collision）：兩個鍵值對應到同一個位置 最壞的情況：退化成 O(N) 搜尋 2019/1/18

53 雜湊法專有名詞 Hash function h(x) Bucket（桶） Home bucket Slot（槽）
Map keys into positions in a table Hash table Bucket（桶） Each position of the hash table Home bucket The position h(x) Slot（槽） The number of elements that a bucket may hold equals the number of slots in the bucket 2019/1/18

54 專有名詞：雜湊表（Hash Table） Hashtable buckets slots 1 2 3 4 5 2019/1/18

55 雜湊法專有名詞 Collision（碰撞） Overflow（溢流） Loading Factor 裝載因子
當h(x1)=h(x2)，x1與x2必須儲存於同一個bucket中 Overflow（溢流） 對同一個bucket的collision數量超過slot的數量時 Loading Factor 裝載因子 Loading Density 裝載密度 =N/(SB) i.e.總資料量/（槽數*桶數） 2019/1/18

56 雜湊函數的設計 設計一函數y=f(x), x,y為正整數 一個好的雜湊函數必須： 通常令x>y Avoid collision
但是：除非事先知道key的分佈狀況，否則collision在所難免 Spread keys evenly in the array Uniform distribution Easy to compute The running time of the hash function should be O(1) 2019/1/18

57 雜湊函數的設計 除法（Division） 中間值法（Mid-Square） 數位分析法（Digit Analysis） 2019/1/18

58 The Division Hash Function
整數除法取餘數 h(x)=x%M Many-to-one mapping 優點 計算容易 M 可以視執行時的情況調整 缺點 連續的key值必轉換至連續的bucket 2019/1/18

59 The Division Hash Function
public class DivisionMethod { static int M = 1031; //質數 public static int h(int x) { return Math.abs(x) % M; } M 值以大於 20 的質數為佳！ 2019/1/18

60 The Division Hash Function
原始資料：8864, 100, 2, 77, 729 h(x) = x % 11 Hash Table 77 100 2 729 8864 1 2 3 4 5 6 7 8 9 10 2019/1/18

61 Middle-Square Method 避免使用除法 事實上所有的整數計算都被迫除以W取餘數，W=2w（w為word size）
整數除法的計算通常比整數乘法慢 事實上所有的整數計算都被迫除以W取餘數，W=2w（w為word size） Hash function 2019/1/18

62 Middle-Square Method public class MiddleSquareMethod {
static int k = 10; // M==1024 static int w = 32; public static int h(int x) { return (x * x) >>> (w - k); } 相當於將接近LSB的 (w-k)個位元除去 >>> 為 arithmetic shift-right 2019/1/18

63 Middle-Square Method 5 1 3 2 4 X 2 6 4 3 5 8 4 9 7 6 X2 超過容量，自動遺失 5 8
3 2 4 X 2 6 4 3 5 8 4 9 7 6 X2 超過容量，自動遺失 5 8 h(X) >>>右移4位 2019/1/18

64 Middle-Square Method 優點 缺點 將連續的key分散投射（Scatter）
Keys with a large number of leading/trailing zeros will collide Middle-square method only consider a subset of the bits in the middle 2019/1/18

65 數位分析法（Digit Analysis）
適合大量靜態資料 分析每一個 Digit 是否均勻分佈，將不均勻分佈的 Digit 刪除，再根據儲存空間的大小決定 Digit 的數目 2019/1/18

66 解決溢位的方法（Overflow Handling）
Linear probing 線性探測 往下找一個空位（到底繞回頭） Rehashing 重覆雜湊 準備多組雜湊函數h1(x),h2(x),h3(x),…,hm(x)，用h1(x)發生溢位，則改用h2(x)，若再發生溢位則改用h3(x)，… 2019/1/18

67 解決溢位的方法（Overflow Handling）
Quadratic probing 平方探測 當 h(x) 溢位，下一次改用 ( h(x) + i2 ) % b 與 ( h(x) – i2 ) % b, 1 i  (b-1)/2 Chaining 鏈結串列 用 Linked-List 解決固定大小的陣列發生溢位的問題 Slot 的數目可動態調整 2019/1/18

68 Linear Probing 線性探測 Linear open addressing 線性開放位址
When home bucket is full, collision item is placed in the next available bucket Regarding the table as circular Clustering problem 搜尋時間變長 2019/1/18

69 Clustering Problem 原始資料：88, 108, 48, 58, 228, 888 h(x) = x % 10
Hash Table 48 58 228 888 88 108 1 2 3 4 5 6 7 8 9 2019/1/18

70 Linear Probing 線性探測 搜尋： Worst case insert and search time: (n)
Start from its home bucket If it is not in its home bucket, Looking forward (circular) until Found! An empty bucket is reached =>element does not exist! Return to the home bucket =>element does not exist! Worst case insert and search time: (n) 2019/1/18

71 Rehashing 重覆雜湊 Use 2 distinct hash functions hi(x)=(h(x)+ih’(x)) mod M
h: K{0,1,…,M-1} h’:K{1,2,…,M-1} hi(x)=(h(x)+ih’(x)) mod M 2019/1/18