資料結構與C++程式設計進階 排序與搜尋 講師：林業峻 CSIE, NTU 6/ 14, 2010.

Presentation on theme: "資料結構與C++程式設計進階 排序與搜尋 講師：林業峻 CSIE, NTU 6/ 14, 2010."— Presentation transcript:

1 資料結構與C++程式設計進階 排序與搜尋 講師：林業峻 CSIE, NTU 6/ 14, 2010

2 大綱 排序 搜尋 泡沫排序法（Bubble Sort） 選擇排序法（Selection Sort）
插入排序法（Insertion Sort） 搜尋 循序搜尋法（Linear Search） 二分搜尋法（Binary Search）

3 排序 (Sorting) 簡介 用途 將一群資料按照某一規則排列，使其具有遞增（減）的關係 資料搜尋 資料的分析與處理 5 1 4 2 3

4 泡沫排序法（Bubble Sort） 使用一迴圈連續對陣列把最大值放到最後 如果有n個數要做n-1次 5個數要做4次 i=5 34 12 5
66 1 i=4 12 5 34 1 66 i=3 5 12 1 34 66 i=2 5 1 12 34 66 i=1 1 5 12 34 66

5 泡沫排序法（Bubble Sort） 把最大值放到最後的方法 將相鄰的資料兩兩比較大小，決定是否交換。 如果有n個數要判斷n-1組數值
5個數要判斷4次 每次都可能交換 swap j=0 34 12 5 66 1 swap j=1 12 34 5 66 1 no swap j=2 12 5 34 66 1 swap j=3 12 5 34 66 1 j=4 12 5 34 1 66

6 泡沫排序法（Bubble Sort） 範例程式碼（將資料由小排到大） #include <stdio.h>
void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void print(int n, int *p) int i; for(i=0; i<n; i++) printf("%d ", p[i]); printf("\n"); int main() { int data[5] = {34,12,5,66,1}; // 欲排序的資料 int i, j; int n=5; for(i=n; i>1; i--) for(j=0; j<i-1; j++) if(data[j+1] < data[j]) swap(&data[j+1], &data[j]); } print(n, data); return 0;

7 選擇排序法（Selection Sort）
如果有n個數要做n-1次 5個數要做4次 i=0 34 12 5 66 1 i=1 1 12 5 66 34 i=2 1 5 12 66 34 i=3 1 5 12 66 34 i=4 1 5 12 34 66

8 選擇排序法（Selection Sort）
在一段資料中找出最大（小）值後，才做交換。 如果有n個數要判斷n-1個數值 5個數要判斷4次 只需交換一次 最小值位置 j=1 34 12 5 66 1 1 j=2 34 12 5 66 1 2 j=3 34 12 5 66 1 2 swap j=4 34 12 5 66 1 4 1 12 5 66 34 4

9 選擇排序法（Selection Sort）
範例程式碼（將資料由小排到大） #include <stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void print(int n, int *p) int i; for(i=0; i<n; i++) printf("%d ", p[i]); printf("\n"); int main() { int data[5] = {34,12,5,66,1}; // 欲排序的資料 int i, j, pos; // pos: 紀錄目前最小值位置 int n=5; for(i=0; i<n-1; i++) pos = i; for(j=i+1; j<n; j++) // 找出最小值 if(data[j] < data[pos]) pos = j; } // 把最小值跟第 i 個做交換 swap(&data[i], &data[pos]); print(n, data); return 0;

10 插入排序法（Insertion Sort）
使用一迴圈連續對陣列的值做插入 如果有n個數要做n-1次 5個數要做4次 key i=1 34 12 5 66 1 key i=2 12 34 5 66 1 key i=3 5 12 34 66 1 key i=4 5 12 34 66 1 i=5 1 5 12 34 66

11 插入排序法（Insertion Sort）
對陣列的值做插入的方法 使用一迴圈將key插到適當的位置 將一段資料中最右(左)邊的資料當作key，然後往左(右)插入 此資料中作排序。 如果有n個數要判斷n-1個數值 資料比對次數較少 適合隨時有新資料需要被插入的應用 要被插入 的值(key) (2) j=0 34 12 5 66 1 12 (1)

12 插入排序法（Insertion Sort）
範例程式碼（將資料由小排到大） #include <stdio.h> void print(int n, int *p) { int i; for(i=0; i<n; i++) printf("%d ", p[i]); } printf("\n"); int main() { int data[5] = {34,12,5,66,1}; // 欲排序的資料 int i, j, key; // key: 紀錄要被插入的值 int n=5; for( i=1; i<n; i++) key=data[i]; for(j=i-1; j>=0 && data[j]>key; j--) data[j+1] = data[j]; } data[j+1] = key; //將key插入 print(n, data); return 0; ……

13 範例 寫一個讓使用者輸入之介面，功能如下 讓使用者任意輸入6個數字，將數字”由大到小” 做排序並將每次排序的結果輸出。 (1) 泡沫排序法
(2) 選擇排序法 (3) 插入排序法 讓使用者任意輸入6個數字，將數字”由大到小” 做排序並將每次排序的結果輸出。 (chap03_ex1.c)

14 範例 寫一個讓使用者輸入之介面，功能如下 (1) 泡沫排序法 (2) 選擇排序法 (3) 插入排序法 讓使用者任意輸入6個字串(字元陣列長度最大 128)，將字串”由英文字母順序大到小”做排序 並將每次排序的結果輸出。 提示: 使用strcmp, strcpy來實作 strcmp(a,b) > 0 : a字串字母順序較大 strcmp(a,b) < 0 : b字串字母順序較大 strcmp(a,b) == 0 : a,b兩字串內容一樣 (chap03_ex2.c)

15 練習: 鏈結串列之插入排序法 寫一個使用者介面，功能如下： (請修改上一章範例chap02_ex.c)
輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於適當位置， 以保持資料由小到大。 輸入f，接著輸入一個整數，印出該整數是否存在鏈結串列中 輸入d，接著輸入一個整數，將鏈結串列中刪除一筆該整數資 料。 輸入l，印出鏈結串列中所有內容。 輸入q後程式結束。 (請修改上一章範例chap02_ex.c) head 插入資料 (key) 30 10 30 50 NULL

16 大綱 排序 搜尋 泡沫排序法（Bubble Sort） 選擇排序法（Selection Sort）
插入排序法（Insertion Sort） 搜尋 循序搜尋法（Linear Search） 二分搜尋法（Binary Search）

17 循序搜尋法（Linear Search） 簡介 範例程式碼 在一群資料中，從頭搜尋到尾直到找到資料為止。
int LinearSearch(int n, int *p, int value) { int i; for(i=0; i< n; i++) if(p[i] == value) return i; // 找到: 傳回資料位置 } return -1; // 找不到: 回傳-1

18 循序搜尋法（Linear Search） 使用迴圈一個一個找資料存放之位置 資料越多找越久… 要找的值 data 34 12 5 66 1
[0] [1] [2] [3] [4] value i data 34 12 5 66 1 [0] [1] [2] [3] [4] i data 34 12 5 66 1 [0] [1] [2] [3] [4] i data 34 12 5 66 1 [0] [1] [2] [3] [4] i data 34 12 5 66 1 [0] [1] [2] [3] [4]

19 二元搜尋法（Binary Search） 簡介 範例程式碼(在一群資料中找出變數key的索引值)
對一群排序過的資料，使用二分法的方式做搜尋。 範例程式碼(在一群資料中找出變數key的索引值) int BinarySearch(int n, int *p, int value) { int low=0, high=n, mid; while(low <= high) mid = (low + high) / 2; if(p[mid] > value) high = mid - 1; else if(p[mid] < value) low = mid+1; else return mid; } return -1;

20 二元搜尋法（Binary Search） 使用二分法找資料 必須確保資料有經過排序 要找的值 data 1 5 12 34 66 34
low mid high data 1 5 12 34 66 34 [0] [1] [2] [3] [4] value low mid high data 1 5 12 34 66 [0] [1] [2] [3] [4] low high mid data 1 5 12 34 66 [0] [1] [2] [3] [4]

21 範例 寫一個讓使用者輸入之介面，功能如下 關鍵: 插入時順便將資料排序 (1) 插入一整數於陣列
(2) 尋找一整數並印出 (使用線性搜尋法) (3) 尋找一整數並印出 (使用二元搜尋法) (4) 印出目前資料(由小到大) 關鍵: 插入時順便將資料排序 (chap03_ex3.c)

22 練習 寫一個讓使用者輸入之介面，功能如下 關鍵: 插入時順便將資料排序 (1) 插入一字串於陣列
(2) 尋找一字串並印出 (使用二元搜尋法) (3) 印出目前資料(由小到大) 關鍵: 插入時順便將資料排序