學習目標

  • 理解插入排序法 (Insertion Sort) 的原理和實作
  • 理解選擇排序法 (Selection Sort) 的原理和實作
  • 掌握兩種排序法的逐步執行過程
  • 能夠分析時間複雜度和空間複雜度
  • 了解兩種排序法的優缺點和適用場景

1. 排序的基本概念

1.1 什麼是排序？

排序 (Sorting) 是將一組資料按照某種順序（遞增或遞減）重新排列的過程。

1.2 排序的分類

  • 穩定排序: 相同值的元素在排序後保持原有相對順序
  • 不穩定排序: 相同值的元素在排序後可能改變相對順序
  • 內部排序: 所有資料都在記憶體中
  • 外部排序: 資料太大，需要用到磁碟

1.3 排序的重要性

排序是電腦科學中最基本的操作之一，許多演算法都依賴於排序後的資料。

2. 選擇排序法 (Selection Sort)

2.1 演算法原理

核心思想: 在每一輪中，從尚未排序的數列中找到最小值，並將其放置到已排序部分的末尾。

2.2 演算法步驟

  1. 將數列分為兩部分：已排序部分（左側）和未排序部分（右側）
  2. 在未排序部分中找到最小值
  3. 將最小值與未排序部分的第一個元素交換
  4. 將該元素視為已排序
  5. 重複步驟 2-4，直到所有元素都排序完成

2.3 逐步執行範例

原始資料: 5, 4, 3, 2, 1

Pass 1: - 未排序部分: 5, 4, 3, 2, 1 - 找到最小值: 1（在位置 4） - 與第一個元素 5 交換 - 結果: 1 | 4, 3, 2, 5 - 說明: | 左側是已排序部分，右側是未排序部分

Pass 2: - 未排序部分: 4, 3, 2, 5 - 找到最小值: 2（在位置 2） - 與第一個元素 4 交換 - 結果: 1, 2 | 3, 4, 5

Pass 3: - 未排序部分: 3, 4, 5 - 找到最小值: 3（在位置 0） - 與第一個元素 3 交換（不移動） - 結果: 1, 2, 3 | 4, 5

Pass 4: - 未排序部分: 4, 5 - 找到最小值: 4（在位置 0） - 與第一個元素 4 交換（不移動） - 結果: 1, 2, 3, 4 | 5

最終結果: 1, 2, 3, 4, 5

2.4 詳細執行過程表

Pass 未排序部分 最小值 交換後結果
初始 5, 4, 3, 2, 1 - 5, 4, 3, 2, 1
1 5, 4, 3, 2, 1 1 (位置 4) 1 \| 4, 3, 2, 5
2 4, 3, 2, 5 2 (位置 2) 1, 2 \| 3, 4, 5
3 3, 4, 5 3 (位置 0) 1, 2, 3 \| 4, 5
4 4, 5 4 (位置 0) 1, 2, 3, 4 \| 5
完成 5 - 1, 2, 3, 4, 5

2.5 虛擬碼 (Pseudocode)

SelectionSort(A[0..n-1])
    for i = 0 to n-2 do
        minIndex = i
        for j = i+1 to n-1 do
            if A[j] < A[minIndex] then
                minIndex = j
        swap A[i] and A[minIndex]

2.6 C 語言實作

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;

    for (i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小值
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 交換
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

2.7 複雜度分析

時間複雜度: - 最壞情況: O(n²) - 需要比較 n(n-1)/2 次 - 最好情況: O(n²) - 即使已經排序，仍需要比較所有元素 - 平均情況: O(n²)

空間複雜度: O(1) - 只需要常數個額外變數

2.8 優缺點

優點: - 實作簡單 - 空間效率高（原地排序） - 交換次數少（最多 n-1 次）

缺點: - 時間複雜度高（O(n²)） - 不穩定（可能改變相同元素的相對順序） - 無論資料是否已排序，都需要 O(n²) 時間

3. 插入排序法 (Insertion Sort)

3.1 演算法原理

核心思想: 將數列分為已排序和未排序兩部分，每一輪從未排序部分取出第一個元素，插入到已排序部分的正確位置。

3.2 演算法步驟

  1. 將第一個元素視為已排序
  2. 從第二個元素開始，逐一處理未排序的元素
  3. 將當前元素與已排序部分的元素從右到左比較
  4. 找到正確位置後，插入該元素
  5. 重複步驟 2-4，直到所有元素都處理完畢

3.3 逐步執行範例

原始資料: 100, 47, 23, 3, 35, 14, 9

Pass 1: - 已排序: 100 - 處理元素: 47 - 比較: 47 < 100，將 47 插入到 100 前面 - 結果: 47, 100 | 23, 3, 35, 14, 9

Pass 2: - 已排序: 47, 100 - 處理元素: 23 - 比較: 23 < 100，繼續；23 < 47，將 23 插入到 47 前面 - 結果: 23, 47, 100 | 3, 35, 14, 9

Pass 3: - 已排序: 23, 47, 100 - 處理元素: 3 - 比較: 3 < 100，繼續；3 < 47，繼續；3 < 23，將 3 插入到最前面 - 結果: 3, 23, 47, 100 | 35, 14, 9

Pass 4: - 已排序: 3, 23, 47, 100 - 處理元素: 35 - 比較: 35 < 100，繼續；35 < 47，將 35 插入到 47 前面 - 結果: 3, 23, 35, 47, 100 | 14, 9

Pass 5: - 已排序: 3, 23, 35, 47, 100 - 處理元素: 14 - 比較: 14 < 100，繼續；14 < 47，繼續；14 < 35，繼續；14 < 23，將 14 插入到 23 前面 - 結果: 3, 14, 23, 35, 47, 100 | 9

Pass 6: - 已排序: 3, 14, 23, 35, 47, 100 - 處理元素: 9 - 比較: 9 < 100，繼續；9 < 47，繼續；9 < 35，繼續；9 < 23，繼續；9 < 14，繼續；9 > 3，將 9 插入到 14 前面 - 結果: 3, 9, 14, 23, 35, 47, 100

最終結果: 3, 9, 14, 23, 35, 47, 100

3.4 詳細執行過程表

Pass 已排序部分 處理元素 插入位置 結果
初始 - - - 100, 47, 23, 3, 35, 14, 9
1 100 47 0 47, 100 \| 23, 3, 35, 14, 9
2 47, 100 23 0 23, 47, 100 \| 3, 35, 14, 9
3 23, 47, 100 3 0 3, 23, 47, 100 \| 35, 14, 9
4 3, 23, 47, 100 35 3 3, 23, 35, 47, 100 \| 14, 9
5 3, 23, 35, 47, 100 14 1 3, 14, 23, 35, 47, 100 \| 9
6 3, 14, 23, 35, 47, 100 9 1 3, 9, 14, 23, 35, 47, 100

3.5 虛擬碼 (Pseudocode)

InsertionSort(A[0..n-1])
    for i = 1 to n-1 do
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key do
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = key

3.6 C 語言實作

void insertionSort(int arr[], int n) {
    int i, j, key;

    for (i = 1; i < n; i++) {
        key = arr[i];  // 要插入的元素
        j = i - 1;

        // 將大於 key 的元素向右移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 插入 key 到正確位置
        arr[j + 1] = key;
    }
}

3.7 複雜度分析

時間複雜度: - 最壞情況: O(n²) - 資料完全逆序，每個元素都需要移動到最前面 - 最好情況: O(n) - 資料已經排序，每個元素只需要比較一次 - 平均情況: O(n²)

空間複雜度: O(1) - 只需要常數個額外變數

3.8 優缺點

優點: - 實作簡單 - 空間效率高（原地排序） - 穩定排序（相同元素保持相對順序） - 適應性強（對已部分排序的資料效率高） - 最好情況只需 O(n) 時間

缺點: - 最壞情況時間複雜度高（O(n²)） - 需要移動元素，可能較慢

4. 兩種排序法的比較

特性 選擇排序 插入排序
時間複雜度（最壞） O(n²) O(n²)
時間複雜度（最好） O(n²) O(n)
時間複雜度（平均） O(n²) O(n²)
空間複雜度 O(1) O(1)
穩定性 不穩定 穩定
交換次數 最多 n-1 次 可能很多次
比較次數 固定 n(n-1)/2 依資料而定
適應性 無（無論資料如何都一樣） 有（已排序資料很快）
實作難度 簡單 簡單

5. 適用場景

5.1 選擇排序適用於

  • 資料量很小（< 50 個元素）
  • 交換成本很高（如排序大型物件）
  • 不需要穩定性

5.2 插入排序適用於

  • 資料量很小（< 50 個元素）
  • 資料已經部分排序
  • 需要穩定性
  • 作為其他排序演算法的子程序（如快速排序的小陣列處理）

6. 練習題

練習題 1

使用選擇排序法排序以下數列，逐步展示過程： 64, 25, 12, 22, 11

解答：

Pass 1: - 未排序: 64, 25, 12, 22, 11 - 最小值: 11 (位置 4) - 交換: 64 ↔ 11 - 結果: 11 | 25, 12, 22, 64

Pass 2: - 未排序: 25, 12, 22, 64 - 最小值: 12 (位置 2) - 交換: 25 ↔ 12 - 結果: 11, 12 | 25, 22, 64

Pass 3: - 未排序: 25, 22, 64 - 最小值: 22 (位置 2) - 交換: 25 ↔ 22 - 結果: 11, 12, 22 | 25, 64

Pass 4: - 未排序: 25, 64 - 最小值: 25 (位置 0) - 不交換 - 結果: 11, 12, 22, 25 | 64

最終: 11, 12, 22, 25, 64

練習題 2

使用插入排序法排序以下數列，逐步展示過程： 12, 11, 13, 5, 6

解答：

Pass 1: - 已排序: 12 - 處理: 11 - 結果: 11, 12 | 13, 5, 6

Pass 2: - 已排序: 11, 12 - 處理: 13 - 結果: 11, 12, 13 | 5, 6

Pass 3: - 已排序: 11, 12, 13 - 處理: 5 - 結果: 5, 11, 12, 13 | 6

Pass 4: - 已排序: 5, 11, 12, 13 - 處理: 6 - 結果: 5, 6, 11, 12, 13

最終: 5, 6, 11, 12, 13

練習題 3

為什麼插入排序在已排序的資料上只需要 O(n) 時間？

解答： 因為在已排序的資料上，每個元素只需要與前一個元素比較一次（發現已經在正確位置），不需要移動任何元素。因此總共只需要 n-1 次比較，時間複雜度為 O(n)。

7. 考試重點提醒

  1. 逐步過程: 要能清楚地展示每一輪的排序過程，用 | 標示已排序和未排序部分
  2. 演算法原理: 理解兩種排序法的核心思想
  3. 複雜度分析: 記住時間和空間複雜度
  4. 穩定性: 插入排序是穩定的，選擇排序不是
  5. 適用場景: 了解何時使用哪種排序法