【Python基礎教學】基本排序法 & 二分搜尋法【part-13】
===
目錄（Table of Contents）
[TOC]
---
哈囉大家好，很感謝你點進本文章，我是一名高中生，是電腦社社團的社長，由於我並不是 Python 這方面非常精通的專家，所以若文章有些錯誤請見諒，也可向我指正錯誤。另外本文章的用意是作為電腦社社團的教材使用而編寫的。
接下來，讓我們進入正題。
排序（Sort）
===
說到排序，我們第一個會想到的那個排序演算法，同時也是最常見最常用的，它就是所謂的「泡沫排序法」或者你也可以說它是「氣泡排序法」都可以，英文都一樣叫作「Bubble Sort」。
而排序在電腦科學中，是指能夠將一串資料依據特定方式排列的演算法。
排列演算法有以下兩種原則：
* 輸出結果是原始資料位置重組的結果
* 輸出結果是「遞增」的序列。
如果我們沒有特別說資料要由小到大還是由大到小排序，那麼排序的預設就會是由小到大（升序）遞增排列。而相反的，如果說要由大到小（降序）排序的話，就需要特別給程式說明這是由大到小排序，而這種形式我們就稱為反向排序（reversed sort）或遞減排序。
排序能夠應用到很多地方，例如：成績排序、排名排序、號碼排序等。
排序也不只能夠使數字進行排序，也能夠對字串進行排序，排序方向是 a-z 排下去。
另外排序不只是單純用來排序而已，它同時也對「搜尋」起到非常大的幫助，若沒有進行排序，在資料量極大（如上千億資料量）的情況下，會很難對某個用戶或是某個資料來進行搜尋，若我們使用線性搜尋的話，可能要花上將近一年的時間去進行搜尋。對資料進行排序過後，再使用二分搜尋演算法的話，可能不到零點幾秒就完成搜尋的動作了，比線性搜尋快八萬倍。
泡沫排序法（Bubble Sort）
---
不曉得各位在 part 10 的時候有沒有看過這一張圖呢？
Image Source：[BUBBLE SORT (Ascendant Algorithm) | by J3 | Jungletronics | Medium](https://medium.com/jungletronics/bubble-sort-ascendant-algorithm-5a3cf7b530f7)
這張圖就是泡沫排序法的執行動畫，可以看見泡沫排序法會先從最左邊開始（索引為 0 時），跟相鄰的資料做對比，如果左邊的比較大，那麼就將右邊的互換，以此類推。
而泡沫排序法如果有 n 筆需要處理的資料，那麼必須比較 n-1 次的迴圈，從索引 0 開始進行比較。
第一次迴圈時，序列中的最大值會被擺放到最右邊，如同 gif 中的 41。
第二次迴圈時，同樣每個元素互相比較，最後產生第二大號，如同 gif 中的 37。
...
最後一次迴圈（第九次迴圈），即產生出最小值 2。
> 泡沫排序法第一次迴圈的比較次數為 n-1 次，第二次為 n-2，到第 n-1 迴圈的時候是 1 次，所以比較總次數計算如下：
(n-1) + (n-2) + ... + 1
所以整體所需時間或稱時間複雜度為 O(n^2)。
泡沫排序法的概念其實非常簡單也非常基礎，接下來就讓我們在 python 上進行實作吧！
要寫泡沫排序法時，我們需要運用到之前的巢狀迴圈之概念，剛剛泡沫排序法中，第一次迴圈需要比較 n - 1 - i 筆資料（隨著最大值固定後，需要比較的項目會越來越少），直到第 n-1 次迴圈為止，而比較這個動作又會用到迴圈，所以我們必須使用巢狀迴圈來解泡沫排序法。
```python=
def bubble_sort(data):
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j] # 進行交換
return data
data = [7,1,2,95,45,20,15,17,33,22]
print(data)
print(bubble_sort(data))
```
首先我們定義一個函數為 bubble_sort() 參數為 data，但這函數只是為了日後方便使用而定義的，你不定義也可。
然後裡面宣告局域變數 n，將序列 data 的長度儲存到 n 裡面作使用。
之後就是執行 n - 1 次的外部迴圈了，而需要透過 n - 1 - i 次的迴圈進行比較，然後這個用於比較的迴圈需要被執行 n - 1 次。
假設序列長度為 5，請看以下示例：
```python=
for i in range(4) # 外部迴圈執行四次
for j in range(n - 1 - i) # 內部迴圈也執行四次
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j] # 進行交換
# 所以會變成這樣:
for j in range(n - 1 - i)
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j] # 進行交換
for j in range(n - 1 - i)
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j] # 進行交換
for j in range(n - 1 - i)
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j] # 進行交換
for j in range(n - 1 - i)
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j] # 進行交換
```
這就是巢狀迴圈的概念，順便替各位複習一下。
除了寫那麼一大長串之外，Python 也有提供排序的方法，叫作 sort()。
語法如下：
```python=
list.sort(key=None, reverse=False)
```
* key -- 主要是用來進行比較的元素，只有一個參數，具體的函數的參數就是取自於可迭代物件中，指定可迭代物件中的一個元素來進行排序。
* reverse -- 排序規則，reverse = True 降序，reverse = False 升序（預設）。
以下是一個範例：
```python=
data = [7,1,2,95,45,20,15,17,33,22]
print(data) # 原始列表
data.sort() # 進行升序排列
print(data) # 印出排列後的列表
data.sort(reverse=True) # 進行降序排列
print(data) # 印出排列後的列表
```
插入排序法（Insertion Sort）
---
Image Source：[Insertion Sort — Swift. Computer science fundamental | by Mahmud Ahsan | Thinkdiff](https://thinkdiff.net/insertion-sort-swift-db14b9a79016)
這個演算法的名稱非常直觀，~~就是插入就對了XD~~
總之呢，這個演算法就是由左至右進行排序，先將左邊的排序完成，再來取右邊尚未排序的數字，在已經排序好的序列中，找一個相對應的地方插入進去，就如同上面的 gif 一樣。
首先第一次迴圈時，會先把索引 0 的 8 當作最小值（以上面那張 gif 為例），呈現灰階，代表已經排列完成。
第二次迴圈取出尚未排序好的最小索引 1，在上面 gif 為 5，拿它來跟已排序好的 8 來作比較，如果 5 比較小，那麼就將它擺放到 8 前面。
第三次迴圈也是一樣，取出未排序好的最小索引 2，在上面 gif 為 3，拿來跟已排序的 8、5 作比較，3 當然是比 5、8 還要小，排序到最左邊去。
接下來以此類推，直到第九次迴圈結束。
在最壞的情況下，插入排序法與泡沫排序法的時間複雜度一樣是 O(n^2)，因為如果第二次迴圈比較 1 次，第三次比較 2 次，比較到第 n 次迴圈比較 n - 1 次，那麼就會是 O(n^2)。
接下來讓我們進行實作吧！
```python=
def insertion_sort(data):
n = len(data)
for i in range(1, n):
for j in range(i, 0, -1):
if data[j] < data[j-1]:
data[j], data[j-1] = data[j-1], data[j] # 互換
else:
break
return data
data = [8,3,5,4,1,2,9,7,6]
print("未排序前：", data)
print("排序後：", insertion_sort(data))
```
首先我們一樣在函數內宣告一變數 n 用來儲存序列 data 的長度。然後插入排序一樣需要使用巢狀迴圈的結構來下去撰寫，但與泡沫排序不同的是，它的第一個 range 寫成這樣：range(1, n)，表示 i 從 1 開始遞增到 n - 1（最後一個索引）。
而下一個迴圈的 range(i, 0, -1)，（i = 1 時）代表 j 值遞減 1 直到 1。
這個寫法也對應到插入排序法的原則，首先索引為 0 的數字就已經預設是排序好的狀態了，所以不需要特別再將它算入未排列的狀況。
所以外層迴圈代表的是執行 i = 1 ~ n - 1 次的迴圈，假設資料長度為 9，那麼這個迴圈會執行 8 次。而內部迴圈的 j 在程式中扮演的角色就是索引位置，因為 i 值最小先從 1 開始，所以 j 就先從 1 開始遞減到 1，由於條件已達成，所以在判斷前後索引值之後，就能夠進行下一個迴圈了（接下來是 i = 2），以此類推。
可以看到判斷的地方一樣是判斷前一個索引跟當前索引值，在插入排序中的圖形，都是以已排序的數字一直進行比較，直到放入對應的位置。
那以上這程式碼解釋差不多就是這樣囉。
選擇排序法（Selection Sort）
---
Image Source：[Insertion Sort, Selection Sort, and Bubble Sort | by Sharad Satsangi | Medium](https://s-satsangi.medium.com/insertion-sort-selection-sort-and-bubble-sort-5eb16d55a4de)
一樣我們先看上面這張 gif 圖，選擇排序的原理是從未排序的序列中找出最小值，然後將這個最小值與最小的索引位置之數字進行對調，就這樣一直做這個動作直到排序結束。
選擇排序法在尋找最小值時，所使用的搜尋法是線性搜尋，線性搜尋在第一次迴圈執行時需要比較 n-1 次，第二次則是 n-2 次，完成整個排序至少需要執行 n-1 次迴圈。
第一次迴圈時，我們看以上 gif 圖，找到最小值 1 後，跟最小索引位置 6 做調換，1 的索引位置移動到 6 來，6 索引位置移動到 1 的索引位置。
第二次迴圈時，接下來找最小值 2，與 8 對調，接下來就以此類推，就請各位同學自行模擬看看囉。
選擇排序法的時間複雜度與上面兩個排序法的時間是一樣的，依舊是 O(n^2)。
接下來廢話不多說，直接進到實作：
```python=
def selection_sort(data):
n = len(data)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if data[min_index] > data[j]:
min_index = j
if i == min_index:
pass
else:
data[i], data[min_index] = data[min_index], data[i]
return data
data = [6,8,3,5,9,10,7,2,4,1]
print(selection_sort(data))
```
我們直接說到 for 迴圈的部分，最外部迴圈就是總體排序所需迴圈次數的部分，並且下一步我們宣告 min_index 作為最小索引被 i 賦值。而內部迴圈則就是線性搜尋的意思了，裡面進行條件判斷，如果最小索引大於當前所遍歷的索引，那麼就將 j 賦值給最小索引 min_index。
小提醒：在這邊要注意的是，我們目前在看的 i、j、min_index 全部都是 data 參數的索引，稍微提醒一下。
好，繼續回到條件判斷的部分，當 data[min_index] > data[j]，那麼就將 min_index = j，這是對的嘛。因為如果遍歷當時的 min_index（最小索引）比 j 索引（i+1 ~ n：在 min_index 的後面）還要大，那麼當然 j 索引就是最小值啦，直接把他替換掉，不過要注意的是，選擇排序法要經過所有資料一輪的比對之後才能得出真正的最小值。
那麼當內層的 for 迴圈結束後，就直接來到判斷的地方了，首先判斷的是如果 i 值等同於 min_index 的話，那麼就不做任何動作，否則資料調換。
這個判斷的意思就是如果目前索引（i）就是最小索引 min_index 那麼就不互換，因為你就已經是最小了，沒有換的必要。
當這個判斷結束後，就會回到外部迴圈，繼續重來上述的所有步驟，一直比對過後，最終就能得到排序結果了。
小結
---
泡沫排序法（Bubble Sort）：前項與後項比較，比較兩者之間的最小值，然後進行對調。
插入排序法（Insertion Sort）：將最小索引當作已排序好的數字，然後將未排序之序列中的最小索引跟已排序好的序列做比較，同樣是找最小值，對調。
選擇排序法（Selection Sort）：線性搜尋出最小值，然後跟當前最小索引進行對調，不斷執行這個步驟，最終得出由小到大的排序。
搜尋（Search）
===
說到搜尋，相信各位第一件事情想的就是 Google，不然就是搜尋引擎這個名詞，而搜尋的定義就是從一個序列中，找出一個指定的值（key）。
接下來我們會介紹兩種基本的搜尋演算法：
* 順序搜尋演算法（或稱：線性搜尋 - Sequential Search、Linear Search）
* 二分搜尋演算法（Binary Search）
順序搜尋（Sequential Search、Linear Search）
---
線性搜尋是最簡單的演算法之一，有多簡單？只要寫幾行 for 迴圈的程式，然後就一個一個遍歷讓他一個一個比對資料值，然後去找他的索引。
這邊我們就不做圖解了，直接進入實作，因為這演算法相信各位只要是明眼人都看得懂。
```python=
def linear_search(data):
for i in range(len(data)):
if data[i] == num:
return i
return -1
data = [7,32,75,4,89,10,22,34,55,23,2,1]
num = int(input("Enter the key:"))
index = linear_search(data)
if index:
print("index: ", index)
else:
print("Couldn't found the key, error: ", index)
```
二分搜尋演算法（Binary Search）
---
二分搜尋演算法（Binary Search），簡稱二分搜，在 APCS 實作中，我們一定、絕對最常用的演算法，請務必將這個演算法牢記。
啊？你說為什麼要學？因為這東西比線性搜尋快上八百倍阿！請看以下 gif：
Image Source：[Binary Search - JavaScript](https://www.doabledanny.com/binary-search-javascript)
看完之後，請你拋棄掉線性搜尋吧，不過也不算是叫做拋棄，如果資料量小的話，而你又怕費事，那你就用線性搜尋沒關係。
但是資料量一大起來的話，假設一億以上，你用線性搜尋可能連明年都還沒算完，而用二分搜的話可能大概不到一秒就找到了。
總之，二分搜的概念其實很簡單，每一次迭代時，都會將索引放到所有元素的中間，然後比較中間值與要找的數，如果比要找的數還要小，那麼就往右邊，否則往左邊。
好，那麼往左往右之後呢？假設我們往左好了，往左是因為中間值比要找的數還小嘛，所以右邊比中間值還大的值就不用看了，之後往左繼續找左邊的中間值，一樣進行比較，直到要找的數為止。
以上面 gif 圖為例：
第一次：target 為 9，首先對所有元素索引除 2，得到中間值為 5，仍然比 9 還要小，所以往右。
第二次：右邊剩下五個元素尚未查找，一樣除於 2，找到中間值為 7，仍然比 9 還要小，繼續往右。
第三次：右邊剩下三個元素尚未查找，一樣除於 2，找到中間值為 8，還是比 9 小。
第四次：再往右的話就發現只剩一個元素了，那麼就是我們要找的值。
而看線性搜尋的地方，需要一個一個找，找到第九次才找得出來。
好的，接下來廢話不多說，直接進入實作：
```python=
def binary_search(data, key):
low = 0
high = len(data) - 1
steps = 0 # 計算二分搜的步驟數
while low <= high:
mid = (low + high) // 2
steps += 1 # 計算步驟數
if data[mid] == key:
return mid, steps
if data[mid] > key:
high = mid - 1
else:
low = mid + 1
return -1, steps
# 資料
data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 目標數字
key = 9
index, steps = binary_search(data, key)
if index:
print(f"使用二分搜找到 {key} 的 index 是 {index}，共花了 {steps} 步驟數")
else:
print(f"指定資料 {key} 不在序列中，{index} 表示找不到，共花了 {steps} 步驟數")
```
看到上面程式碼，首先函數內宣告 low、high 變數與 steps 變數，steps 可加也可不加，只是為了要計算它的步驟次數。
而 low、high 的意思就代表上面所說的「往左、往右」，其實就是「索引」往左往右的意思。
那麼在這邊使用的是 while 迴圈，條件為 low <= high 時執行迴圈內容，如果 low 大於等於 high 那麼就跳出迴圈，return -1, steps，表示找不到跟執行的步數。
那麼我們來看迴圈內容：
首先宣告變數 `mid = (low + high) // 2`，至於為什麼要用 // 運算子呢？以下是使用除法運算子的錯誤訊息，請看：
```python=
Traceback (most recent call last):
File "C:\Users\LukeTseng\Downloads\a.py", line 22, in <module>
index, steps = binary_search(data, key)
File "C:\Users\LukeTseng\Downloads\a.py", line 9, in binary_search
if data[mid] == key:
TypeError: list indices must be integers or slices, not float
```
這個 mid 就很好懂了吧，數學上學過中點的公式：兩者相加除於 2，得到中點。
小補充：像是 C、C++ 語言實作這類的演算法，因為會直接宣告其資料型態是 int，是不帶有小數點的，所以會用 `mid = (low + high) / 2`。
然後判斷序列的中間值是否等於、是否大於、是否小於指定值。如果等於，那麼就表示已經找到啦，就不用繼續搜尋了，直接回傳索引。如果大於，那麼就往左（high = mid - 1），如果小於，那麼就往右（low = mid + 1）。
中間值 - 1，就表示往左，因為索引變小了；中間值 + 1，就表示往右，因為索引變大了。
總結
===
BS：泡沫排序法
IS：插入排序法
SS：選擇排序法
| 排序演算法 | 時間複雜度（最壞情況） | 時間複雜度（平均情況） | 時間複雜度（最佳情況） | 空間複雜度 | 穩定性 | 適用情況 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| BS | O(n^2) | O(n^2) | O(n) | O(1) | 穩定 | 資料量小且幾乎有序 |
| IS | O(n^2) | O(n^2) | O(n) | O(1) | 穩定 | 資料量小且幾乎有序 |
| SS | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩 | 資料量小 |
| 搜尋演算法 | 時間複雜度（最壞情況） | 時間複雜度（平均情況） | 時間複雜度（最佳情況） | 適用資料結構 | 適用情況 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 順序搜尋法 | O(n) | O(n) | O(1) | 序列 | 資料無須排序 |
| 二分搜尋法 | O(log n) | O(log n) | O(1) | 排序過的序列 | 資料已排序 |
名詞由來：順序搜尋演算法的另稱為線性搜尋，可以從時間複雜度看到呈現 O(n)，也就是時間「線性」成長。而二分搜尋演算法則是因為不斷平均的結果下去搜尋。
泡沫排序法（Bubble Sort）：資料前後比對，大者往後，小者往前。
插入排序法（Insertion Sort）：把序列中的索引 0，開頭元素作為最小值，每次搜索所有資料進行比較，比索引值小就塞到前面。
選擇排序法（Selection Sort）：先從序列中找出最小值，然後將這個最小值與最小的索引位置之數字進行在已排序的序列進行對調，重複此動作直到排序完成。
順序搜尋法（Linear Search）：逐個比較資料，以此來尋找資料。
二分搜尋法（Binary Search）：前提是必須要有已排序好的資料才能搜尋，搜尋方法為將資料索引一分為二，通常看資料大小，如果資料比較大，則會往右找，小則往左，無論往左往右，索引繼續一分為二，重複上述動作。
參考資料
===
[[演算法] 二分搜尋 (Binary Search) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10206818)
[二分搜尋法（Binary Search）完整教學（一）- 基礎介紹 | AppWorks School](https://medium.com/appworks-school/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%B8%80-%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-dd2cd804aee1)
[【Day30】[演算法]-線性搜尋法Linear Search - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/m/articles/10280298)
[Binary Search - JavaScript](https://www.doabledanny.com/binary-search-javascript)
[Python 演算法筆記 — 選擇排序法. 選擇排序法(Selection Sort) | by 保羅楊 | Keroro | Medium](https://medium.com/kkproject/python-%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E6%B3%95-b6e65213afba)
[【Day22】[演算法]-選擇排序法Selection Sort - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/m/articles/10276719)
[Insertion Sort, Selection Sort, and Bubble Sort | by Sharad Satsangi | Medium](https://s-satsangi.medium.com/insertion-sort-selection-sort-and-bubble-sort-5eb16d55a4de)
[[演算法] 泡沫排序 (Bubble Sort) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10202160)
[泡沫排序 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F)
[Python3 List sort()方法 | 菜鳥教程](https://www.runoob.com/python3/python3-att-list-sort.html)
[【筆記】Sorting 排序 – Yui Huang 演算法學習筆記](https://yuihuang.com/sorting/)
[Insertion sort (插入排序法). Insertion sort… | by Oliver Liao | Medium](https://medium.com/@ollieeryo/insertion-sort-%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-c215ae516a7a)
[Insertion Sort — Swift. Computer science fundamental | by Mahmud Ahsan | Thinkdiff](https://thinkdiff.net/insertion-sort-swift-db14b9a79016)
[【Day23】[演算法]-插入排序法Insertion Sort - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10277360)
書籍：演算法：圖解邏輯思維 + Python程式實作 王者歸來
Sign in with Wallet
Connect another wallet