【Python進階教學】進階排序法：快速排序法 / 合併排序法【part 17】
===
目錄（Table of Contents）
[TOC]
---
哈囉大家好，很感謝你點進本文章，我是一名高中生，是電腦社社團的社長，由於我並不是 Python 這方面非常精通的專家，所以若文章有些錯誤請見諒，也可向我指正錯誤。另外本文章的用意是作為電腦社社團的教材使用而編寫的。
那麼，讓我們開始吧。
快速排序法（Quick Sort）
===
（快速排序法概念圖）Image Source：[Unraveling QuickSort: The Fast and Versatile Sorting Algorithm | by Nathal Dawson | Medium](https://medium.com/@nathaldawson/unraveling-quicksort-the-fast-and-versatile-sorting-algorithm-2c1214755ce9)
快速排序法步驟：
1. 序列中尋找一個基準值（pivot）
2. 進行快速排序法，所有比基準值小的排左邊，比他大的排右邊。
3. 使用遞迴式對左右兩邊的子序列作與 2. 相同排序。
註：基準值可使用隨機的抽取方式，或是自定義一個基準值。
看到這邊，或許你發現到快速排序法其實類似於二分法的步驟，只不過特別的是，快速排序法需要使用到遞迴式，這個概念使用到了所謂的 ***分治法（divide and conquer）*** 的其中一種。
讓我們舉個具體的例子，以上面的概念圖為例：
首先概念圖取 3 作為快速排序法中的基準值，
所以，比 3 小的排左邊，像是 -3、2、-6、1；比 3 大的排右邊，像是 8、5、9、6。
左右兩邊分別再次取基準值，跟前面步驟做一樣的事情：
* 第一次左分支：
取最右邊 1 作為基準值，進行排序，同樣比它小排左邊，比它大排右邊。左：-3、-6；右：2（只剩一個就不須再分）
* 第一次右分支：
取最右邊 6 作為基準值，進行排序，同樣比它小排左邊，比它大排右邊。左：5（只剩一個就不須再分）；右：9、8
* 第二次左分支：
取 -6 作為基準值，分為 -6、-3，不能再分了，結束。
* 第二次右分支：
取 8 作為基準值，分為 8、9，不能再分了，結束。
那最後我們的程式會自動將這排序好的結果（只看單一方塊的那個數字就是排序好的）遞迴回去，像是 -6、-3；8、9 是已經排序好的，把它遞迴回去，最後排序完成：-6、-3、1、2、3、5、6、8、9。
以下是快速排序法的重點：
快速排序法中，選擇基準值是非常重要的一件事情，如果沒選對基準值的話，這個方法的時間複雜度為 O(n^2)。如果選對的話，時間複雜度則會降為 O(n log n)。
Python 實作
---
以下範例程式碼參考自書籍：演算法：圖解邏輯思維 + Python程式實作王者歸來
```python=
import random
def quick_sort(nLst):
if len(nLst) <= 1:
return nLst
left = []
right = []
piv = []
pivot = random.choice(nLst)
for val in nLst:
if val == pivot:
piv.append(val)
elif val < pivot:
left.append(val)
else:
right.append(val)
return quick_sort(left) + piv + quick_sort(right)
data = [9, -3, 5, 2, 6, 8, -6, 1, 3]
print("原始列表 :", data)
print("排序結果 :", quick_sort(data))
```
程式碼解釋：
* line 1 : 引入 random 隨機亂數模組
* line 3 ~ 4 : 判斷 nLst 長度是否只有 1，是的話就回傳 nLst 列表本身。
* line 6 ~ 8 : 初始化局域變數 left, right, piv，這邊其實可使用多變數賦值方式：left = right = piv = []
* line 9 : 使用 random.choice(seq) 方法，seq 為一個序列，功能為在序列當中隨機取一項元素，再回傳那個元素。
* line 10 : 遍歷 nLst 列表。
* line 11~12 : 判斷 val 如果等同於 pivot（基準值），則將 val 塞到 piv 列表的最末尾。
* line 13~14 : 判斷 val 是否小於 pivot，是的話就將 val 塞到 left 列表的最末尾（小的在左邊）。
* line 15~16 : 由於上述條件不成立，最後肯定判斷 val 是大於 pivot 的，則將 val 塞入 right 列表的最末尾（大的往右邊）。
* line 17 : 回傳 quick_sort(left) + piv + quick_sort(right)，進行遞迴式，列表相加的意義為列表之間互相連接，彷彿兩個斷裂的橋樑再次接合一樣。
小結
---
快速排序法步驟：
1. 序列中尋找一個基準值（pivot）
2. 進行快速排序法，所有比基準值小的排左邊，比他大的排右邊。
3. 使用遞迴式對左右兩邊的子序列作與 2. 相同排序。
時間複雜度：
* 選對基準值：O(n log n) -> 效率佳
* 選錯基準值：O(n^2) -> 效率差
合併排序法（Merge Sort）
===
（合併排序法 gif 概念動圖）Image Source：[Merge Sort | Sorting Algorithm | Code Pumpkin](https://codepumpkin.com/merge-sort-sorting-algorithm/)
合併排序法演算法的精神與快速排序法是相同的，同屬於分治法（divide and conquer）。
合併排序法主要是先將序列進行 ***分割（divide）*** 成近乎等長的兩序列，重複處理至序列只剩下一個元素，直到無法再被分割，這點與快速排序法是相同的。
分割完之後呢，接下來進行 ***合併（conquer）*** 被分割的序列，主要將已排序好的最小單位之數列開始合併，重複處理到合併與原序列相同長度的序列。
再整理一下：
合併排序法主要動作為 ***分割（divide）、合併（conquer）***。
* 分割（divide）：把序列平分（//2，只取整數），接著繼續將各個平分後的序列繼續切，切到不能再切為止（剩下 1 個元素）。
* 合併（conquer）：把這些已排序最小單位的序列（就是那個切到不能再切的序列）合併，重複合併到與原序列相同大小。
接下來讓我們演示一下分割的步驟，如下圖：
接著繼續切，如下圖：
還是繼續切，切到個數與原序列的個數相同。
切到如上圖這樣，分割基本上就完成了。
接下來合併起來：
等下你就會發現，這個排序法會在合併的時候進行排序。
所以合併是進行排序的過程。
合併排序法的時間複雜度是 O(n log n)。因為資料有 n 個，所以可以建立 log n 的階層樹，無論怎麼去建立，都必須處理 n 個數，所以時間複雜度才是 O(n log n)。
Python 實作
---
以下範例程式碼參考自書籍：演算法：圖解邏輯思維 + Python程式實作王者歸來
```python=
def merge(left, right):
''' 兩數列合併 '''
output = []
while left and right:
if left[0] <= right[0]:
output.append(left.pop(0))
else:
output.append(right.pop(0))
if left:
output += left
if right:
output += right
return output
def merge_sort(nLst):
''' 合併排序 '''
if len(nLst) <= 1:
return nLst
mid = len(nLst) // 2
left = nLst[:mid]
right = nLst[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
data = [4, 1, 7, 5, 3, 2, 6]
print("原始串列 :", data)
print("排序結果 :", merge_sort(data))
```
程式碼解釋：
* Line 3 : 初始化 output 變數。
* Line 4 : while 迴圈，判斷 left、right 存在，則執行迴圈。
* Line 5 ~ 6 : 判斷 left[0] <= right[0]，成立則將 left.pop(0) 取出 left 第一個值後回傳的值放入 output 當中。
* Line 7 ~ 8 : 否則將 right.pop(0) 取出 right 第一個值後回傳的值放入 output 當中。
* Line 9 ~ 10 : 如果 left 存在，output 與 left 列表連結。
* Line 11 ~ 12 : 如上。
* Line 13 : 回傳 output 列表值。
* Line 19 : 定義 mid 變數為 len(nLst) // 2，求取列表長度除於 2 的值，只取整數。
* Line 20 : left = nLst[:mid] 擷取列表值，從 0 開始直到 (mid - 1) 索引。
* Line 21 : right = nLst[mid:] 擷取列表值，從 mid 索引開始直到末尾的索引。
* Line 22 ~ 23 : 遞迴，進行分割動作。
* Line 24 : 回傳 merge(left, right) 合併排序後的結果。
小結
---
合併排序法主要動作為 ***分割（divide）、合併（conquer）***。
* 分割（divide）：把序列平分（//2，只取整數），接著繼續將各個平分後的序列繼續切，切到不能再切為止（剩下 1 個元素）。
* 合併（conquer）：把這些已排序最小單位的序列（就是那個切到不能再切的序列）合併，重複合併到與原序列相同大小。
時間複雜度：O(n log n)
總結
===
在排序上通常都預設升序排序，也就是由小到大，所以一定都要有個概念：小的排左邊，大的排右邊。
| 屬性 | 快速排序法（Quick Sort） | 合併排序法（Merge Sort） |
| -------- | -------- | -------- |
| 基本概念 | 基於選擇基準值（pivot）將數列分為小於基準值和大於基準值的子序列，然後遞迴排序。 | 將數列分割成兩半，遞迴排序各半部，然後合併已排序的子序列。 |
| 排序策略 | 分治法：分割、排序、合併 | 分治法：分割、合併 |
| 時間複雜度 | 最壞情況 O(n²)；平均情況 O(n log n) | O(n log n) |
| 空間複雜度 | O(log n)（在原地排序，不需要額外空間） | O(n)（需要額外空間來儲存中間結果） |
| 穩定性 | 不穩定（相同值的順序可能會改變） | 穩定（相同值的順序不變） |
| 適用情況 | 當空間有限或不需要穩定排序時效果較好 | 當需要穩定排序或有大量數據時效果較好 |
| 基準值選擇 | 隨機選擇或選擇特定位置的元素作為基準值 | X |
| 分割過程 | 依據基準值分為左右兩部分，左側小於基準值，右側大於基準值 | 將數列平分成兩半，直到每個部分僅含一個元素 |
| 合併過程 | 合併步驟在遞迴回程中自然完成 | 將已排序的兩個子序列合併成一個完整的排序序列 |
參考資料
===
書籍：演算法：圖解邏輯思維 + Python程式實作王者歸來
[初學者學演算法｜排序法進階：合併排序法. 程式麻瓜的程式知識課（六） | by Cheng-Wei Hu | 胡程維 | AppWorks School | Medium](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e)
[【Day25】[演算法]-合併排序法Merge Sort - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10278179)
[Merge Sort | Sorting Algorithm | Code Pumpkin](https://codepumpkin.com/merge-sort-sorting-algorithm/)
[Unraveling QuickSort: The Fast and Versatile Sorting Algorithm | by Nathal Dawson | Medium](https://medium.com/@nathaldawson/unraveling-quicksort-the-fast-and-versatile-sorting-algorithm-2c1214755ce9)
[[演算法] 快速排序法 (Quick Sort) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10202330)
[Python choice() 函数 | 菜鸟教程](https://www.runoob.com/python/func-number-choice.html)
Sign in with Wallet
Connect another wallet