基礎排序：O(n²) 排序演算法#

基礎排序演算法時間複雜度為 O(n²)，適用於小規模資料。雖然效率不高，但實作簡單，是學習排序的起點。

核心概念#

有序度與逆序度#

  • 有序度：陣列中有序元素對的數量，滿足 a[i] <= a[j] 且 i < j
  • 滿有序度：完全有序時的有序度 = n*(n-1)/2
  • 逆序度 = 滿有序度 - 有序度

排序的本質就是增加有序度、減少逆序度，直到達到滿有序度。

冒泡排序 (Bubble Sort)#

每次比較相鄰元素，將較大者「冒泡」到右側。

特性說明
時間複雜度最好 O(n)、最壞/平均 O(n²)
空間複雜度O(1)，原地排序
穩定性穩定
冒泡排序程式碼
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 優化：無交換代表已有序
            break
    return arr

插入排序 (Insertion Sort)#

將陣列分為「已排序區」與「未排序區」，逐一將未排序元素插入正確位置。

特性說明
時間複雜度最好 O(n)、最壞/平均 O(n²)
空間複雜度O(1)，原地排序
穩定性穩定
插入排序程式碼
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
    return arr

為何插入排序優於冒泡排序？

兩者時間複雜度相同，但冒泡的「交換」需要 3 次賦值，插入的「移動」只需 1 次。實測顯示，插入排序比冒泡排序快約 3-7 倍。

選擇排序 (Selection Sort)#

每次從未排序區選出最小元素，放到已排序區末尾。

特性說明
時間複雜度最好/最壞/平均皆為 O(n²)
空間複雜度O(1)，原地排序
穩定性不穩定
選擇排序程式碼
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]
    return arr

選擇排序是不穩定的！例如 [5, 8, 5, 2, 9]，第一次選擇最小值 2 與第一個 5 交換後，兩個 5 的相對順序改變了。

實務應用建議#

  1. 小規模資料：插入排序是首選
  2. 幾乎有序的資料：插入排序效率接近 O(n)
  3. 工業級排序函式：當區間元素 <= 4 時，通常切換為插入排序
Backward 排序演算法 進階排序 Forward