第六章-排序、搜尋

排序 Sort

搜尋次數多n*(n+1)/2 - 1、交換次數過多。

氣泡排序的兩種寫法

1.兩層迴圈、遞增、從0 ~ n-1向後逐一檢查交換。

2.由0開始相鄰兩兩檢查、遞增、從n-1 ~ 1大的往後交換。

搜尋次數多n*(n+1)/2 - 1、交換次數為較少的 n - 1。

選擇排序的兩種寫法

1.內層負責記錄最小值位置，結束內層才交換至前面位置。(前面位置會逐次往後+1)

2.由0開始記錄最大值位置，結束內層才交換至後面位置。(後面位置會逐次向前-1)

搜尋次數少( n - 1 )、搬移次數不一定。

搜尋方式divide and conquer、交換次數不一定。

1.數列中選擇一元素作為基準點(pivot)。

2.小於此元素的移至基準的左邊，大於此元素的移至右邊，相等的任意放。

3.基準點左邊和右邊視為兩個數列，並重複做以上動作直到數列剩下一個或零個元素。

循序搜尋 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迴圈