# 基礎演算法 線性搜尋, 二元搜尋, 選擇排序, 泡沫排序, 合併排序
###### tags: `Algorithm`
## 線性搜尋法(Linear Search)
假設我們有一個含有n個元素的陣列(沒有經過排序)，我們並不知道每一個元素具體的數值為和，假設我們想要在這個陣列當中找到特定的數值，最簡單的方法便是由左到右找一次，直到找到我們想要找到的數值為止(因為我們的陣列未經排序)。
而這樣的行為，使用虛擬碼(pseudocode)來表示，可以寫成
```c=
For i from 0 to n–1
If number behind i'th door
Return true
Return false
```
> 1.我們對每一個元素(視為房間)，將每一間房間都標記上房號，從0到n - 1號，然後依序確認
> 2.我們在for迴圈中依序把每一間房間都檢視過一遍，如果有找到，則回傳ture，沒有則跳出for，回傳false
> 3.而這個演算法的時間複雜度為O(N)(worst case)，而他的下界會是Ω(1)(best case)
> 你可能要找的數字在最後一號(worst case)，也有可能在第一個位置(best case)
如果我們已經知道這一陣列已經經過排序，則我們可以從陣列的最中間開始找起，可以獲得更高的效率。
程式碼實作
```c=
int main(void) {
int array[10] = {0,1,2,3,4,5,6,7,8,9};
int size = sizeof(array) / sizeof(int);
int target = 0;
scanf("%d", &target);
printf("target = %d", Linear_search(array, size, target));
}
int Linear_search(int *array, int size, int target)
{
for(int i = 0; i < size; i++)
{
if(array[i] == target)
{
return array[i];
}
}
return -1;
}
```
## 二元搜尋法(Binary Search)
如果給定的陣列是已經經過排序(由小到大)，則我們可以使用比Linear Search還要更高效率的方法，Binary Search，找到陣列中的中間元素，如果我們要找的元素比中間元素小，則向左邊找。如果我們要找的元素比中間元素大，則向右邊找。如果一開始就沒有任一扇門存在，則回傳false。
而這樣的行為，使用虛擬碼(pseudocode)來表示，可以寫成
```c=
If no doors
Return false
If number behind middle door
Return true
Else if number < middle door
Search left half
Else if number > middle door
Search right half
```
> 1.時間複雜度O(log(n))(worse case)，Ω(1)(best case)
> 2.假設現在有64個元素，我們可以注意到，使用Binary Search所需的步驟數遠少於Linary Search
> Binary Search : 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
> Linary Search : 64 -> 63 -> 62 -> 61 ....
程式碼實作
```c=
int main(void) {
int array[10] = {0,1,2,3,4,5,6,7,8,9};
int size = sizeof(array) / sizeof(int);
int target = 0;
scanf("%d", &target);
printf("size = %d\n", size);
printf("target = %d", Binary_search(array, size, target));
}
int Binary_search(int *array, int size, int target)
{
int max = size - 1;
int min = 0;
while(max >= min)
{
int mid = (min + max) / 2;
if(array[mid] == target)
{
return array[mid];
}
else if(array[mid] < target)
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
return -1;
}
```
## 選擇排序法(Selection Sort)
在上面的例子中，如果我們要加快搜尋陣列中的某一個元素，我們會使用Binary Search來取代Linear Search，但是，使用Binary Search的條件為陣列中的元素必須是經過排序的，所以，如果我們想要加快搜尋陣列中某一個元素的速度，我們必須要先將陣列進行排序後，以便我們搜尋陣列中的元素，這裡將介紹選擇排序法(Selection Sort)。
如果我們現在有一組陣列[4,2,7,1,6,3,5]，對其進行選擇排序法(Selection Sort)如下
> 首先，我們先選出陣列中最小的元素，從0號看到n - 1號，我們可以找到1，我們將1從陣列中取出
> [4,2,7,X,6,3,5] 手上:1
> 由於1是目前的最小值，我們必須將它放在0號的位置，以符合由小到大的排序方法，因此，我們將在0號的元素4，給取出
> [X,2,7,X,6,3,5] 手上:4,1
> 將1放到原先4所在的位置
> [1,2,7,X,6,3,5] 手上:4
> 將4放回原本1所在的位置
> [1,2,7,4,6,3,5]
>
> 再次進行排序，第一個數字已經排序過，故我們從1號看到n - 1號，找出陣列中最小的元素，元素為2，並取出
> [1,X,7,4,6,3,5] 手上:2
> 將2放到目前最左邊的位置以符合由小排到大的要求
> [1,2,7,4,6,3,5]
>
> 再次進行排序，第一個數字和第二個數字已經經過排序，故我們從2號看到n - 1號，找出陣列中最小的元素，找到元素為3，並取出
> [1,2,7,4,6,X,5] 手上: 3
> 由於要求為由小到大進行排序，我們將7號元素取出
> [1,2,X,4,6,X,5] 手上: 3,7
> 將3放入原先7的位置
> [1,2,3,4,6,X,5] 手上: 7
> 將7放回原本3所在的位置
> [1,2,3,4,6,7,5]
>
> 以此類推已完成排序
[視覺化選擇排序法](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
而這樣的行為，使用虛擬碼(pseudocode)來表示，可以寫成
```c=
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item
```
> 1.使用for迴圈找到0號到n - 1號陣列中，最小的元素
> 2.找到最小元素後，和第i號元素進行交換，如上方演示所示
> 3.在這個演算法中，我們在n個元素中找出最小元素，並進行了n次，時間複雜度大約為O(n^2^)，而Ω(n^2^)，可見在最理想的情況下，我們仍然需要N^2^
> 證明:
> 我們查詢所有元素n，然後n - 1，然後n - 2....
> n + (n - 1) + (n - 2) ...
> -> n(n + 1) / 2
> -> (n^2 + n) / 2
> 在n趨近於無限大的情況下，該數值逼近於n^2
> 故時間複雜度為O(N^2)
程式碼實作
```c=
int main(void) {
int array[7] = {4,2,7,1,6,3,5};
int size = sizeof(array) / sizeof(int);
Selection_sort(array, size);
show(array, size);
return 0;
}
void Selection_sort(int *array, int size)
{
int min_id = 0;
for(int i = 0; i < size - 1; i++)
{
min_id = i;
for(int j = i + 1; j < size; j++)
{
if(array[j] < array[min_id])
{
min_id = j;
}
}
swap(&array[min_id], &array[i]);
}
}
void show(int *array, int size)
{
for(int i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
```
## 泡沫排序法(Bubble sort)
我們將介紹另外一種排序法，被稱為泡沫排序法(Bubble Sort)
如果我們現在有一組陣列[4,2,7,1,6,3,5]，對其進行泡沫排序法(Bubble Sort)如下
> 挑選第0號元素4，4比2大，故兩者交換 [2,4,7,1,6,3,5]
> 挑選第1號元素4，4比7小，故不交換 [2,4,7,1,6,3,5]
> 挑選第2號元素7，7比1大，故交換 [2,4,1,7,6,3,5]
> 挑選第3號元素7，7比6大，故交換 [2,4,1,6,7,3,5]
> 挑選第4號元素7，7比3大，故交換 [2,4,1,6,3,7,5]
> 挑選第5號元素7，7比5大，故交換 [2,4,1,6,3,5,7]
> 經過第一次排序後，我們已經將最大的元素放到最末端
> 剩下以此類推後，即可完成排序
[視覺化排序法](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
而這樣的行為，使用虛擬碼(pseudocode)來表示，可以寫成
```
Repeat until sorted
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
```
> 1.由於我們比較的為第i個元素和第i + 1個元素，因此我們只需要找0到n - 2號
> 2.在每一次排序，最大的數字都會被移動到最右方。
> 3.時間複雜度O(N^2^)，Ω(N)，在Best case，看過整個陣列是否需要swaps即可。
程式碼實作
```c=
#define swap(x, y) {int temp; temp = x; x = y; y = temp;}
void Bubble_sort(int *, int);
void show(int *, int );
int main(void) {
int array[7] = {4,2,7,1,6,3,5};
int size = sizeof(array) / sizeof(int);
Bubble_sort(array, size);
show(array, size);
return 0;
}
void Bubble_sort(int *array, int size)
{
for(int i = 0; i < size - 1; i++)
{
for(int j = 0; j < size - i - 1; j++)
{
if(array[j] > array[j + 1])
{
swap(array[j], array[j + 1]);
}
}
}
}
void show(int *array, int size)
{
for(int i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
}
```
## 合併排序法(Merge sort)
如果有兩筆或以上的資料，而這些資料位於不同的陣列或是檔案中，我們要如何為它們進行排序？
這時我們可以使用Merge sort，其原理為將兩個**已經排好序**的陣列，將兩者合併後進行排序。
但如果兩個陣列本身沒有經過排序，是否還能使用合併排序法呢? 答案是肯定的，我們知道對長度越短的陣列進行排序，所花費的時間越少，我們可以將想要排序的陣列，不斷的拆分為兩等分，直到剩下一個元素，再來進行合併排序。
而這樣的策略，又被稱為分治法(Divide-and-Conquer)。
Divide:將原問題猜分若干個子問題
Conquer:使用遞迴的方式解決子問題，當子問題足夠簡單時則能夠直接解
Combine:將子問題的解不斷合併，得到原問題的解
而Merge Sort即是Divide-and-Conquer的應用之一，而進行的步驟如下
1.先將目前的array拆分成兩個array
2.將兩個sub array進行Merge sort
3.直到sub array只有一個元素，即將兩個sub array合併成新的sub array
而這樣的行為，使用虛擬碼(pseudocode)來表示，可以寫成
```c=
If only one number
Return
Else
Sort left half of number
Sort right half of number
Merge sorted halves
```
假設我們要使用Merge sort排序array:[6 3 8 5 2 7 4 1]
1.拆分array成sub array
```
6 3 8 5 | 2 7 4 1
```
2.將sub array拆分為sub array
```
6 3 | 8 5
```
3.將sub array拆分為sub array
```
6 | 3
```
4.現在兩個sub array都只剩下一個元素，表示他們已經完成排序，這時候我們將他們進行merge，並生成新的sub array
```
_ _ 8 5 2 7 4 1
3 6
```
5.將2.的sub array拆分為sub array
```
8 | 5
```
6.現在兩個sub array都只剩下一個元素，表示他們已經完成排序，這時候我們將他們進行merge，並生成新的sub array
```
_ _ _ _ 2 7 4 1
3 6 | 5 8
```
7.sub array[3, 6]和sub array[5, 8]皆已完成排序，這時候我們將他們進行merge，並升成新的sub array
```
_ _ _ _ _ _ _ _
_ _ _ _ 2 7 1 4
3 5 6 8
```
8.對1.產生右邊的sub array也徒同上面的步驟進行排序，我們會得到兩個已經經過排序的sub array
```
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
3 5 6 8 | 1 2 4 7
```
9.將兩個sub array進行merge，完成整個array的sorted
```
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
1 2 3 4 5 6 7 8
```
圖解如下:
程式碼實作
```c=
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int head, int mid, int tail);
void merge_sort(int arr[], int head, int tail);
void input_list(int arr[], int);
void show_list(int arr[], int count);
// Merge two subarrays of A[].
// First subarray is arr[head..mid]
// Second subarray is arr[mid+1..tail]
int main()
{
int count;
scanf("%d", &count); //讀入陣列的大小
int *list = (int *)malloc(sizeof(int) * count);
printf("Numbers to be sorted: ");
input_list(list, count);
show_list(list, count);
printf("\n");
merge_sort(list, 0, count - 1);
printf("Numbers Sorted: ");
show_list(list, count);
return 0;
}
void merge(int arr[], int head, int mid, int tail)
{
int lenA = mid - head + 1;
int lenB = tail - (mid + 1) + 1;
int *A = (int*)malloc(sizeof(int) * lenA); //First sub array
int *B = (int*)malloc(sizeof(int) * lenB); //Second sub array
//Copy data to temp arrays A[] and B[]
int i, j, k;
for (i = 0; i < lenA; i++)
{
A[i] = arr[head + i]; //複製資料到左鎮列
}
for (j = 0; j < lenB; j++)
{
B[j] = arr[mid + 1 + j]; //複製資料到右陣列
}
// Merge two temp arrays back into arr[head..tail]
i = 0;
j = 0;
k = head;
//while array A and B haven't finished scanning
while (i < lenA && j < lenB)
{
if (A[i] < B[j])
{
arr[k] = A[i];
i++;
}
else
{
arr[k] = B[j];
j++;
}
k++;
}
//Copy the remaing elements into arr[], if A[] haven't finished scanning
while (i < lenA)
{
arr[k] = A[i];
i++;
k++;
}
//Copy the remaing elements into arr[], if B[] haven't finished scanning
while (j < lenB)
{
arr[k] = B[j];
j++;
k++;
}
}
void merge_sort(int arr[], int head, int tail)
{
if (head < tail)
{
int mid = (head + tail) / 2;
merge_sort(arr, head, mid);
merge_sort(arr, mid + 1, tail);
merge(arr, head, mid, tail);
}
}
void show_list(int arr[], int count)
{
for (int i = 0; i < count; i++)
{
printf("%d ", arr[i]);
}
}
void input_list(int arr[], int count)
{
for (int i = 0; i < count; i++)
{
scanf("%d", &arr[i]);
}
}
```
程式碼行為:
假設Input 為[6 3 2]
> merge_sort(arr, 0, 2)
> if(head(0) < tail(2))成立
> mid = (2 + 0) / 2 = 1
> 呼叫merge_sort(arr, 0, 1)
>> if(head(0) < tail(1))成立
>> mid = (0 + 1) / 2 = 0
>> 呼叫merge_sort(arr, 0, 0)
>>> if(head(0) < tail(0))不成立
>>>
>> 呼叫merge_sort(arr, 1, 1)
>>
>>> if(head(1) < tail(1))不成立
>>>
>> 呼叫merge(arr, 0, 0, 1)
>>
>>> lenA = mid(0) + head(0) + 1 = 1, lenB = tail(1) - (mid(0) + 1) + 1 = 1
>>> 分別將資料複製到左陣列Ａ和右陣列Ｂ
>>> A[] = {6}, B[] = {3}
>>> while(i(0) < lenA(1) && j(0) < lenB(1))
>>>> if(A[0] (6) < B[0] (3))不成立
>>>> else arr[0] = B[0], arr[] = {3,3,2}
>>>>
>>> k++ = 1，表示arr已寫入元素，j++表示Ｂ陣列元素已寫入arr
>>> while(i(0) < lenA(1) && j(1) < lenB(1))不成立
>>> 將還沒寫入arr的元素寫入到arr中
>>> while(i(0) < lenA(1))成立
>>>> arr[1] = A[0], arr[] = {3, 6, 2}
>>>>
>>> while(j(1) < lenB(1))不成立
>>>
>> merge_sort(arr, 2, 2)
>>> if(head(2) < tail(2))不成立
>>>
>> merge(arr, 0, 1, 2)
>>> lenA = mid(1) + head(0) + 1 = 2, lenB = tail(2) - (mid(1) + 1) + 1 = 1
>>> 別將資料複製到左陣列A[]和和右陣列B[]
>>> A[] = {3,6}, B[] = {2}
>>> while(i(0) < lenA(2) && j(0) < lenB(1))
>>>> if(A[0] (3) < B[0] (2))不成立
>>>> else arr[0] = B[0], arr[] = {2,3,6}, k++ = 1, j++ = 1
>>>>
>>> while(i(0) < lenA(2) && j(1) < lenB(1))不成立
>>> 將還沒寫入arr的元素寫入arr中
>>> while(i(0) < lenA(2))
>>>> arr[1] = A[0], arr[] = {2,3,6}
>>>>
>>> while(i(1) < lenA(2))
>>>> arr[2] = A[1], arr[] = {2,3,6}
>>>>
>>> while(i(2) < lenA(2))不成立
>>> while(j(1) < lenB(1))不成立
>>>
>> 到這裡arr已經完成排序
參考資料: 大話數據結構，C语言程序设计现代方法第2版，IT Home，圖片源於網路
Sign in with Wallet
Connect another wallet