使用C++實現插入排序算法

什麼是插入排序？¶

插入排序是一種簡單直觀的排序算法，它的核心思想就像我們平時整理撲克牌：將一張新牌插入到已排好序的牌堆中合適的位置，直到所有牌都排好序。在計算機中，就是將數組中的每個元素逐個插入到它前面已排序的子數組中，直到整個數組有序。

插入排序的基本思路¶

假設我們有一個數組arr，要將其從小到大排序，步驟如下：

初始狀態：數組的第一個元素（索引0）默認是“已排序”的，因爲只有一個元素時天然有序。
逐個插入：從第二個元素（索引1）開始，依次處理每個元素：
- 取出當前元素arr[i]，臨時保存其值（避免後續移動元素時被覆蓋）。
- 從已排序的子數組末尾（即i-1位置）開始，向前比較：如果前面的元素arr[j]比當前元素大，就將arr[j]後移一位（騰出位置）。
- 重複上述比較和移動，直到找到第一個比當前元素小的元素arr[j]，此時將臨時保存的元素插入到j+1位置。
循環結束：所有元素處理完畢後，數組自然有序。

算法實現步驟（C++代碼）¶

下面通過代碼實現上述思路，註釋會詳細解釋每一步的作用：

#include <iostream>
using namespace std;

// 插入排序函數：參數爲數組arr和長度n
void insertionSort(int arr[], int n) {
    // 外層循環：從第二個元素開始（i=1），到最後一個元素（i=n-1）
    for (int i = 1; i < n; i++) {
        int temp = arr[i];  // 臨時保存當前要插入的元素，避免被覆蓋
        int j = i - 1;      // j指向已排序子數組的最後一個元素

        // 內層循環：向前比較，找到插入位置
        // 條件：j >= 0（未越界）且arr[j] > temp（前面元素比當前大，需要後移）
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];  // 前面元素後移一位
            j--;                  // 繼續向前比較
        }

        // 找到插入位置，將temp放入正確位置
        arr[j + 1] = temp;
    }
}

int main() {
    // 測試用例：待排序數組
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);  // 計算數組長度

    // 打印排序前的數組
    cout << "排序前：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // 調用插入排序函數
    insertionSort(arr, n);

    // 打印排序後的數組
    cout << "排序後：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

代碼邏輯詳解¶

1. 外層循環（處理每個待插入元素）¶

從i=1開始遍歷數組（因爲索引0是初始已排序的）。
對於每個i，當前元素是arr[i]，需要找到它在已排序子數組中的正確位置。

2. 內層循環（尋找插入位置）¶

temp = arr[i]：臨時保存當前元素，避免後續移動元素時被覆蓋。
j = i - 1：從已排序子數組的末尾開始向前比較。
while (j >= 0 && arr[j] > temp)：
如果前面的元素arr[j]比當前元素temp大，說明需要後移arr[j]（騰出位置）。
執行arr[j+1] = arr[j]後，j自減1，繼續向前比較。
當循環結束時，j+1就是temp的正確插入位置，執行arr[j+1] = temp。

示例：手動模擬排序過程¶

以數組[5, 2, 4, 6, 1, 3]爲例，逐步演示排序過程：

初始數組：[5, 2, 4, 6, 1, 3]（已排序子數組：[5]）
處理i=1（元素2）：
- temp=2，j=0（已排序子數組末尾）。
- arr[j]=5 > 2，所以arr[1]=5，j=-1。
- 插入後：arr[0]=2，數組變爲[2, 5, 4, 6, 1, 3]。
處理i=2（元素4）：
- temp=4，j=1（已排序子數組末尾是5）。
- arr[j]=5 > 4，所以arr[2]=5，j=0（arr[j]=2 <= 4）。
- 插入後：arr[1]=4，數組變爲[2, 4, 5, 6, 1, 3]。
後續步驟：繼續處理i=3（6）、i=4（1）、i=5（3），最終數組變爲[1, 2, 3, 4, 5, 6]。

複雜度分析¶

時間複雜度：
最壞情況：數組逆序（如[5,4,3,2,1]），需要O(n²)次比較和移動。
最好情況：數組已排序（如[1,2,3,4,5]），內層循環僅需1次比較，時間複雜度O(n)。
空間複雜度：僅需臨時變量temp，空間複雜度O(1)（原地排序）。

適用場景¶

插入排序適合小規模數據（如n<1000）或基本有序的數據（此時接近O(n)效率）。它的優點是簡單直觀、穩定（相等元素相對位置不變），但對於大規模數據，效率不如快速排序、歸併排序等高級算法。

總結¶

插入排序的核心是“逐個插入”，通過將每個元素插入到已排序子數組的正確位置實現整體有序。C++實現時，只需用兩層循環（外層遍歷元素，內層移動元素）即可完成。雖然代碼簡單，但要注意邊界條件（如j=-1時的插入處理）和臨時變量的使用，避免數據覆蓋。掌握插入排序是理解更復雜排序算法的基礎。