[Algorithm] 排序演算法

演算法概念

排序就是把一堆資料照大小排好，好處是之後查詢、去重、找中位數都便宜。評估一個排序演算法要看四件事：時間（多快）、空間（要不要多開陣列）、穩定性（相等元素順序會不會被打亂）、適應性（資料已經接近有序時會不會更快）。

比較型排序（靠比誰大誰小決定順序）的理論下界是 $O(n \log n)$，因為 $n!$ 種排列要用二元判斷樹區分，至少要 $\log_2 n! = \Theta(n \log n)$ 次比較。想突破這個下界只能用非比較型（counting/radix/bucket），但那些有額外假設。

穩定性的例子：[('Alice', 90), ('Bob', 80), ('Charlie', 90)] 依分數升序，Alice 和 Charlie 同分，穩定排序後 Alice 仍在 Charlie 前面。

各適用情境

泡泡排序（Bubble Sort）

演算法策略

相鄰兩個比一比，大的往右推。一輪下來最大的值就冒到最右定位。每輪少掃一個（右邊已定位的不用再比），直到某一輪沒發生任何交換就提早結束。

變數：$i$ 是外層輪次（代表右邊已有 $i$ 個定位），$j$ 是內層指標從 0 掃到 $n - 1 - i$。

複雜度

最壞每輪掃 $n - 1, n - 2, \ldots, 1$ 次 → $\frac{n(n-1)}{2} = O(n^2)$。最佳情況（已排序）一輪就發現沒 swap、提早結束 → $O(n)$。就地、穩定。

範例

題目：[4, 1, 3, 1, 5, 2] 由小到大排序。

圖解：

步驟：

第 1 輪（$i = 0$）：$j$ 掃 0 到 4。

5 冒到最右。

第 2 輪（$i = 1$）：$j$ 掃 0 到 3。

第 3 輪（$i = 2$）：$j$ 掃 0 到 2。

第 4 輪（$i = 3$）：全程無 swap → 提早結束。最終 [1, 1, 2, 3, 4, 5]。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

選擇排序（Selection Sort）

演算法策略

每輪從未排序區找最小值，跟未排序區的第一個位置交換。左邊已排序區每輪長一格，右邊縮一格。

變數：$i$ 是外層輪次（也是未排序區起點）、$j$ 從 $i + 1$ 掃到末端、min_idx 記當輪最小值位置。

複雜度

無論輸入如何，外層 $n - 1$ 輪、內層每輪平均掃 $n/2$ 次 → 一律 $O(n^2)$。好處是交換次數最少（每輪一次），壞處是不穩定——[3a, 3b, 1] 第 1 輪把 $3a$ 換到位置 3，就跳到 $3b$ 後面了。

範例

題目：[4, 1, 3, 1, 5, 2] 由小到大排序。

圖解：

步驟：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

插入排序（Insertion Sort）

演算法策略

想像整理撲克牌：左手已排好的牌堆、右手再抽一張新的，往左找適當位置插進去。程式上把新元素 key 暫存，左邊比它大的往右推一格，直到找到不比它大的位置，塞回去。

複雜度

最佳情況（已排序）每次只比較一次 → $O(n)$。最壞情況（逆序）每個新元素都要推到最前面 → $O(n^2)$。就地、穩定、適應性強——資料越接近有序越快，Python 的 Timsort 內部就用它處理小區段。

範例

題目：[4, 1, 3, 1, 5, 2] 由小到大排序。

圖解：

步驟（左邊為已排序部分）：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

合併排序（Merge Sort）

演算法策略

分而治之：把陣列從中間切成兩半，各自遞迴排序，再把兩個已排序的小陣列合併——兩邊用指標各指一個元素，誰小誰先寫進結果陣列。一路拆到單元素（天然有序），再一路合回去。

複雜度

遞迴式 $T(n) = 2T(n/2) + O(n)$，主定理 Case 2 → $O(n \log n)$。遞迴樹 $\log n$ 層，每層合計掃 $n$ 個元素 → $n \log n$。不論輸入如何都一樣快。穩定、但要 $O(n)$ 額外空間存合併結果。

範例

題目：[4, 1, 3, 1, 5, 2] 由小到大排序。

圖解：

步驟（分解 → 合併）：

分解階段：[4, 1, 3, 1, 5, 2] → [4, 1, 3] + [1, 5, 2] → 再切成 [4]、[1, 3]、[1]、[5, 2] → 最後到單元素 [4]、[1]、[3]、[1]、[5]、[2]。

合併階段：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

快速排序（Quick Sort）

演算法策略

挑一個基準值（pivot），把陣列分成「比 pivot 小」、「等於 pivot」、「比 pivot 大」三堆，對左右兩堆遞迴。實務上最常用，常數係數小、cache 友好。

關鍵是 pivot 選得好不好：永遠選第一個，遇到已排序輸入時會退化成 $O(n^2)$。實務用隨機選或三數取中（median-of-three）來避免 worst case。

複雜度

平均情況 pivot 把陣列切成接近均等的兩半：$T(n) = 2T(n/2) + O(n) = O(n \log n)$。最壞情況 pivot 每次都是極值：$T(n) = T(n - 1) + O(n) = O(n^2)$。不穩定（partition swap 會打亂相等元素順序）。

範例

題目：[4, 1, 3, 1, 5, 2] 由小到大排序，選中間元素為 pivot。

圖解：

步驟：

合併：[1, 1] + [2] + [3] + [4] + [5] = [1, 1, 2, 3, 4, 5]。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

總比較

實務選擇：

• 資料量小或幾乎有序 → Insertion
• 要穩定且資料量大 → Merge
• 一般最快 → Quick + 隨機 pivot
• Bubble / Selection → 只拿來教學

常見考法