插入排序法

前導

插入排序（Insertion Sort），它的概念類似於撲克牌整理，我們拿起一張牌並將它插入到已排序的牌堆中，使整堆牌仍然保持有序。

演算法流程

假設陣列長度為n，我們要做的就只是將陣列中的元素，逐一與已排序好的資料做比較。

實際範例

[12, 11, 13, 5, 6]

排序步驟：

1. 第一次迭代（i = 1）：
2. • 當前要插入的元素(未排序區域的第一個元素)：11
   • 已排序區域：[12]
   • 比較：11 與 12 比較，因 11 < 12
   • 將 12 向右移動，並在最前面插入 11
   • 結果：[11, 12, 13, 5, 6]
2. 第二次迭代（i = 2）：
3. • 當前要插入的元素(未排序區域的第一個元素)：13
   • 已排序區域：[11, 12]
   • 比較：13 與 12 比較，因 13 ≥ 12，不需要移動
   • 結果保持不變：[11, 12, 13, 5, 6]
3. 第三次迭代（i = 3）：
4. • 當前要插入的元素(未排序區域的第一個元素)：5
   • 已排序區域：[11, 12, 13]
   • 比較過程： 5 < 13 → 繼續比較 5 < 12 → 繼續比較 5 < 11 → 繼續比較...
   • 將 5 插入最前面，因為離開迴圈，arr[-1 + 1] = key;
   • 結果：[5, 11, 12, 13, 6]
4. 第四次迭代（i = 4）：
5. • 當前要插入的元素(未排序區域的第一個元素)：6
   • 已排序區域：[5, 11, 12, 13]
   • 比較過程： 6 < 13 → 繼續比較 6 < 12 → 繼續比較 6 < 11 → 繼續比較 6 ≥ 5 → 找到插入位置
   • 將 6 插入在 5 與 11 之間
   • 結果：[5, 6, 11, 12, 13]

最終排序結果：

[5, 6, 11, 12, 13]

程式碼

#include <stdio.h>

// 插入排序函式
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 當前要插入的數
        int j = i - 1;

        // 向右移動比 key 大的元素，為 key 騰出位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  
            j--;  //繼續比較，向左遍歷已排序部分的陣列，找到合適的位置來插入 key。
        }

        arr[j + 1] = key;  // 插入 key
    }
}

// 輔助函式：列印陣列
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主程式
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: ");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("排序後: ");
    printArray(arr, n);
    return 0;
}