C語言插入排序算法詳解與實現

插入排序 是一種直觀且易於理解的排序算法。其核心思想是：將數組分為「已排序區間」和「未排序區間」，初始時已排序區間只有一個元素，然後依次從未排序區間取出元素，在已排序區間中找到合適位置插入，並保持已排序區間有序。這就像我們整理撲克牌時，抓到一張牌就插入到手中已排好序的牌的合適位置一樣。

算法步驟

1. 從數組第二個元素（索引 1）開始，將其視為待插入元素 x。
2. 在已排序區間（索引 0 到 i-1）中從右向左掃描，找到第一個小於等於 x 的元素位置。
3. 將掃描過程中遇到的所有大於 x 的元素向右移動一位，騰出空位。
4. 將 x 插入空位，完成一輪插入。
5. 重複上述過程，直到所有元素處理完畢。

代碼實現

#include 
#include 
#include 

#define N 10

int main() {
    int a[N] = {-1, 3, 6, 9, 13, 22, 27, 32, 49}; // 預留一個空位給待插數
    int x, j, k;

    srand((unsigned)time(NULL));
    x = rand() % 100;
    printf("隨機產生 x 的值為: %d\n", x);

    // 若 x 大於當前最大值，直接放入預留位置
    if (x > a[N-2]) {
        a[N-1] = x;
    } else {
        // 查找待插位置
        j = 0;
        while (j <= N-2 && x > a[j]) {
            j++;
        }
        // 從後向前移動元素，騰出位置
        for (k = N-2; k >= j; k--) {
            a[k+1] = a[k];
        }
        a[j] = x; // 插入待插數
    }

    printf("排序後輸出:\n");
    for (j = 0; j <= N-1; j++) {
        printf("%d ", a[j]);
    }
    printf("\n");
    return 0;
}

運行結果示例

隨機產生 x 的值為: 15
排序後輸出:
-1 3 6 9 13 15 22 27 32 49 

算法特性分析

優化方向

• 二分查找插入位置：將查找位置的 O(n) 降為 O(log n)，但移動元素仍需 O(n)，整體仍為 O(n²)。
• 希爾排序：插入排序的改進版，通過分組跳躍式移動元素，大幅提升效率。

總結

插入排序雖然時間複雜度為平方級，但代碼簡潔、穩定、適應性強（對近乎有序數據接近 O(n)），是小規模數據排序的首選。理解其「插入」與「移位」的核心邏輯，有助於掌握更高級的排序算法。