使用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时的插入处理）和临时变量的使用，避免数据覆盖。掌握插入排序是理解更复杂排序算法的基础。