iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 3
3

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

快速排序 (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

接下來就看程式碼吧~

程式時間複雜度 O(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]

動手做做看吧~

拉蒙碎碎念

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


上一篇
[演算法] 泡沫排序 (Bubble Sort)
下一篇
[演算法] 基數排序法 (Radix Sort)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言