CodeGym /課程 /Python SELF TW /快速排序

快速排序

Python SELF TW

等級 58 , 課堂 4

開放

9.1 快速排序的定義

快速排序 (Quick Sort) 是一種有效的排序算法，使用“分而治之”的方法。其運作原理是選擇一個支點元素 (pivot)，將數組分成兩個子數組：小於支點的元素和大於支點的元素，然後對每個子數組遞歸應用同一過程。

快速排序算法誕生於試圖解決「如何更快地將小元素移到左邊，大元素移到右邊」的問題。假設我們最小的元素在最右邊，能否快速將其移到接近其最終位置？這將大幅減少不必要的比較次數。

運作原理：

1. 選擇支點元素 (pivot)：

從數組中選擇一個元素作為支點。這可以是第一個元素、最後一個元素、中間元素或隨機元素。有時選擇三個隨機元素的平均值。

2. 分割 (partitioning)：

把所有小於支點的元素移到數組左邊，而所有大於支點的元素移到右邊。結果是支點在排序後的數組中位於其最終位置。

3. 遞歸應用：

遞歸對左子數組和右子數組應用該過程，不包括支點元素。

步驟過程

選擇支點元素。
移動小於支點的元素到左邊，大於的元素到右邊。
遞歸應用處理子數組。

快速排序的時間和空間複雜度

時間複雜度：

最壞情況: O(n^2) — 發生在每次選擇了最糟糕的支點（例如，數組已經排序）。
平均情況: O(n log n) — 對於隨機分佈的數據。
最好情況: O(n log n) — 每次數組可以平分。

空間複雜度：

O(log n) — 需要存儲遞歸調用的堆棧，如果使用了尾遞歸且支點選得好。

9.2 快速排序算法的實現

Python 實現：


def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # 基本情況：有 0 或 1 個元素的數組已經排序
    
    pivot = arr[len(arr) // 2]  # 選擇支點元素
    left = [x for x in arr if x < pivot]  # 小於支點的元素
    middle = [x for x in arr if x == pivot]  # 等於支點的元素
    right = [x for x in arr if x > pivot]  # 大於支點的元素
    
    return quick_sort(left) + middle + quick_sort(right)

# 使用示例：
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序後的數組:", sorted_arr)
# 輸出: 排序後的數組: [1, 1, 2, 3, 6, 8, 10]

算法示例

以數組為例: [3, 6, 8, 10, 1, 2, 1]

第一次遍歷：

支點元素: 8
左側元素: [3, 6, 1, 2, 1]
中間元素: [8]
右側元素: [10]

遞歸排序左側部分 [3, 6, 1, 2, 1]:

支點元素: 1
左側元素: []
中間元素: [1, 1]
右側元素: [3, 6, 2]

遞歸排序右側部分 [3, 6, 2]:

支點元素: 6
左側元素: [3, 2]
中間元素: [6]
右側元素: []

遞歸排序左側部分 [3, 2]:

支點元素: 2
左側元素: []
中間元素: [2]
右側元素: [3]

合併結果: [1, 1, 2, 3, 6] 為左側部分, [10] 為右側部分, 中間是 [8]。