## 演算法筆記｜快速排序法（ Quick Sort ）

### 複習
上次提到了[泡沫排序法](https://hackmd.io/4XnyNFnUTrOJ37Rtp3cCiA)這個演算法，如果還沒看或有興趣的讀者可以去看看唷！

<br/>

### 基本觀念

&emsp;&emsp;快速排序法的重點是要從數列中挑選一個<font color="#0000FF">基準</font>（pivot），然後重新排列數列，將比基準小的放左邊，比基準大的放右邊，如果與基準相同則放左右都可以，接著對左右的子序列做遞迴重複剛剛的2步驟，直到子序列數量剩0或1個元素。再來為大家演示實際上如何運作。

<br/>

### 圖解快速排序法

（1）數列裡有數字1~9隨機排列。


（2）<font color="#f00">隨機</font>選擇一個基準（pivot）4，將比4小的放左邊，比4大的排至右邊，形成2個子序列。
（3）重複以上步驟，從左右子序列中各選出一個基準，若排列到該子序列剩下的元素為0個或1個就停止。
（4）順帶一提，每一個子序列的基準都是隨機選擇的唷～
（5）差不多完成了
（6）完成，將所有的元素整理一下

<br/>

### 時間複雜度計算

| | 最佳解 | 平均解 | 最差解 |
| -------- | -------- | ---------- | --- |
| 時間複雜度 | $O(n)=nlogn$ | $O(n)=nlogn$ | $O(n)=n^2$ |

<br/>

### 快速排序法實作

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 = [8, 1, 5, 6, 4, 7, 3, 9]
print("原始串列：",data)
print("排序結果：",quick_sort(data))

下圖是快速排序法輸出的結果，有興趣的讀者也可以自己試試看唷～