Alg2.2. 快速排序法

快速排序法使用到遞迴及分治法 (divide and conquer) 的概念，其中分治法的部份完成下列兩個步驟：

• 確定基本情況：指必須使用最單純的基本情況 (或問題無法再被分割)。
• 分割或縮減問題：指將問題轉換成基本情況。

若以由小到大排序數值串列為例，首先，對一個串列取一個中心點來將串列分割 (partition) 成三個部份：小於中心點數值的元素 (左半邊)、中心點數值及大於中心點數值的元素 (右半邊)。接下來，左右半邊元素的子串列再各自再進行分割 (即遞迴情況)，直到不需要分割的情況時回傳原本的串列結果 (即基本情況)。

快速排序法的基本情況有下列兩種情況：

• 空串列: [ ]
• 只有一個元素的串列: [ x ]

因此，快速排序法的遞迴概念整理如下：

def partition(array):
    if 條件式:
        # 基本情況
        return array
    else:
        # 遞迴情況
        return partition(left_array) + mid_array + partition(right_array)

• 參考檔案：quick_sort.py

# 匯入模組
import random as r                                    # 使用隨機亂數模組
from datetime import datetime
r.seed(datetime.now())                                # 設定亂數模組


# 定義函數
def quick_sort(data):
    if len(data) < 2:                                 # 基本情況, 當輸入的串列長度小於2
        return data                                   # 回傳原來輸入的串列
    else:
        small_part = []                               # 遞迴情況, 分割串列
        big_part = []

        # pivot = data[0]                             # 固定選取中心點或
        pivot = data[r.randint(0, len(data) - 1)]     # 隨機選取中心點

        for i in range(0, len(data)):                 # 分割串列
            if data[i] == pivot:                      # 忽略中心點
                pass
            else:
                if data[i] <= pivot:                  # 小於中心點數值的元素存入左半邊串列
                    small_part.append(data[i])
                else:
                    big_part.append(data[i])          # 大於中心點數值的元素存入右半邊串列
                                                      # 對左右半邊的串列進行遞迴呼叫
        return quick_sort(small_part) + [pivot] + quick_sort(big_part)


# 呼叫函數
data = [10, 5, 2, 3]
print(data)
print(quick_sort(data))


# 執行結果
[10, 5, 2, 3]
[2, 3, 5, 10]

躍躍欲試

• 使用上述的快速排序法:
  • d550: 物件排序 [參考答案] ★★★, practice

參考資料

• 寫程式前就該懂的演算法, 第四章, Aditya Y.Bhargava著, 張書華譯, 松崗, ♥️