有鑒於昨天學的泡沫排序法，效率篇低，就有某位聰明的科學家發明了快速排序法，其實也有用到一點二元分類的概念。

快速排序 (Quick Sort) 的想法是說，先找一個基準點，然後派兩個代理人分別從資料的兩邊開始往中間找，如果右邊找到一個值比基準點小，左邊找到一個值比基準點大，就讓他們互換。反覆找並互換，直到兩個人相遇。然後再將相遇的點跟基準點互換。第一輪結束。

原始狀態： 基準點 + 一堆資料......
第一輪後的狀態： 比基準點小的資料 ＋ 基準點 ＋ 比基準點大的資料

接下來再分別從兩邊資料做子循環，但做法跟上面一樣，這就用到了遞迴的概念。

較小資料： (小)基準點 + 小資料 --> 小小資料 + (小)基準點 + 小大資料
較大資料： (大)基準點 + 大資料 --> 大小資料 + (大)基準點 + 大大資料

接下來就重複以上的動作，直到排列完畢。

• 直接用例子來說明好了。一樣用身高來比大小，分為 1~10。假設基準點為 8。

8　6　1　10　5　3　9　2　7　4

• 從兩邊開始找。左邊找比基準點大，右邊找比基準點小。

8　6　1　10　5　3　9　2　7　4
8　6　1　10　5　3　9　2　7　4
8　6　1　10　5　3　9　2　7　4

• 然後互換。

8　6　1　4　5　3　9　2　7　10

• 繼續往下找

8　6　1　4　5　3　9　2　7　10
8　6　1　4　5　3　9　2　7　10
8　6　1　4　5　3　9　2　7　10

• 再互換

8　6　1　4　5　3　7　2　9　10

• 繼續往下找，但左右代理人相遇在 2。

8　6　1　4　5　3　7　2　9　10

• 與基準點互換

2　6　1　4　5　3　7　8　9　10

• 分為兩個子循環。

( 2　6　1　4　5　3　7 ) 　　+　　8 (基準點)　　+ 　　( 9　10 )

• 再分別重複以上動作。

較小資料：2　6　1　4　5　3　7
較大資料：9　10
.
.
黑箱作業
.
.
最終結果：
1　2　3　4　5　6　7　8　9　10

接下來就看程式碼吧～

程式時間複雜度 Ｏ(NlogN)

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def quicksort(data, left, right): # 輸入資料，和從兩邊開始的位置
    if left >= right :            # 如果左邊大於右邊，就跳出function
        return

    i = left                      # 左邊的代理人
    j = right                     # 右邊的代理人
    key = data[left]                 # 基準點

    while i != j:                  
        while data[j] > key and i < j:   # 從右邊開始找，找比基準點小的值
            j -= 1
        while data[i] <= key and i < j:  # 從左邊開始找，找比基準點大的值
            i += 1
        if i < j:                        # 當左右代理人沒有相遇時，互換值
            data[i], data[j] = data[j], data[i] 

    # 將基準點歸換至代理人相遇點
    data[left] = data[i] 
    data[i] = key

    quicksort(data, left, i-1)   # 繼續處理較小部分的子循環
    quicksort(data, i+1, right)  # 繼續處理較大部分的子循環

quicksort(data, 0, len(data)-1)
print(data)

結果為：

data = [23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

動手做做看吧～

拉蒙碎碎念

第一次參加鐵人賽，每天都要出文章其實壓力蠻大的，畢竟手頭上還有幾個項目要做。
就努力堅持完賽吧！
大家加油！！！