插入排序算法原理與 C 語言完整實現

編輯：關於C語言

插入排序：從有序序列中插入新元素的經典算法

插入排序是一種簡單直觀的排序算法，其核心思想是將待排序陣列分為「已排序區」與「未排序區」，每次從未排序區取出一個元素，在已排序區中找到合適位置插入，並將後續元素後移。本文詳細拆解插入邏輯、邊界處理，並提供完整可運行的 C 語言代碼。

算法步驟圖解

初始狀態：假設前 k 個元素已有序（arr[0..k-1]）。
取出待插元素：key = arr[k]。
從右向左掃描有序區：i = k-1，當 arr[i] > key 時，將 arr[i] 後移至 arr[i+1]，i--。
插入：循環結束時 i+1 即為插入位置，arr[i+1] = key。
重複：對 k = 1 .. n-1 執行上述過程。

完整 C 語言實現

#include <stdio.h>

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 將大於 key 的元素依次後移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 插入
    }
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {2, 3, 5, 11, 15, 17}; // 已排序陣列
    int n = 6;
    int key;
    printf("原始陣列: ");
    print_array(arr, n);

    printf("請輸入要插入的數: ");
    scanf("%d", &key);

    // 擴充陣列空間（此處為演示固定大小 7）
    int new_arr[7];
    for (int i = 0; i < n; i++) new_arr[i] = arr[i];
    new_arr[n] = key; // 先放到末尾
    insertion_sort(new_arr, n + 1); // 對 n+1 個元素排序

    printf("插入後陣列: ");
    print_array(new_arr, n + 1);
    return 0;
}

關鍵點解析

邊界條件：j >= 0 確保不越界；若所有元素都大於 key，循環結束時 j = -1，插入位置 0 正確。
穩定性：條件 arr[j] > key（非 >=）保證相等元素不交換順序，屬穩定排序。
原地排序：空間複雜度 O(1)，僅需常數額外空間。

複雜度分析

情況	時間複雜度	說明
最好	O(n)	陣列已有序，內層循環零次執行
最壞	O(n²)	陣列逆序，每次需掃描整個有序區
平均	O(n²)	隨機資料約需 n²/4 次比較與移動
空間	O(1)	原地排序