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

基本觀念

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

圖解快速排序法

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

（2）隨機選擇一個基準（pivot）4，將比4小的放左邊，比4大的排至右邊，形成2個子序列。

（3）重複以上步驟，從左右子序列中各選出一個基準，若排列到該子序列剩下的元素為0個或1個就停止。

（4）順帶一提，每一個子序列的基準都是隨機選擇的唷～

（5）差不多完成了

（6）完成，將所有的元素整理一下

時間複雜度計算

快速排序法實作

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))

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