第六章-排序、搜尋
排序 Sort
排序 Sort
氣泡排序 Bubble Sort
氣泡排序 Bubble Sort
搜尋次數多n*(n+1)/2 - 1、交換次數過多。
氣泡排序的兩種寫法
1.兩層迴圈、遞增、從0 ~ n-1向後逐一檢查交換。
2.由0開始相鄰兩兩檢查、遞增、從n-1 ~ 1大的往後交換。
選擇排序 Select Sort
選擇排序 Select Sort
搜尋次數多n*(n+1)/2 - 1、交換次數為較少的 n - 1。
選擇排序的兩種寫法
1.內層負責記錄最小值位置,結束內層才交換至前面位置。(前面位置會逐次往後+1)
2.由0開始記錄最大值位置,結束內層才交換至後面位置。(後面位置會逐次向前-1)
插入排序 Insert Sort
插入排序 Insert Sort
搜尋次數少( n - 1 )、搬移次數不一定。
快速排序 Quick Sort
快速排序 Quick Sort
搜尋方式divide and conquer、交換次數不一定。
1.數列中選擇一元素作為基準點(pivot)。
2.小於此元素的移至基準的左邊,大於此元素的移至右邊,相等的任意放。
3.基準點左邊和右邊視為兩個數列,並重複做以上動作直到數列剩下一個或零個元素。
搜尋 Search
搜尋 Search
循序搜尋 Sequential
原始未排序資料宣告:int data[5]={8,5,10,1,7};
[練習題]:輸入目標值,以循序方式搜尋數字陣列,顯示其位置或找不到。
二元搜尋 Binary
原始已排序資料宣告:int data[13]={12,13,27,34,39,42,58,60,67,71,88,92,95};
[練習題]:輸入目標值,以二元方式搜尋數字陣列,顯示其位置或找不到。
循序搜尋
循序搜尋
使用for迴圈
二元搜尋
二元搜尋
使用while迴圈