🧮 C++ 插入排序（Insertion Sort）通俗易懂教程 🚀

📌 包含静态数组 + vector 实现，支持下标从 0 和 1 开始的版本！

---

🎯 一、什么是插入排序？

插入排序（Insertion Sort） 是一种简单直观的排序算法。它的原理是：

把一个元素插入到已经排好序的序列中，使其保持有序性。

你可以把它想象成你整理扑克牌的过程：
🃏 每次拿到一张新牌，你就把它插入到已有的牌中合适的位置。

---

🧱 二、插入排序的特点 ✨

特点	说明
时间复杂度	最坏情况 $O(n^2)$，最好情况 $O(n)$
空间复杂度	$O(1)$ 原地排序
稳定性	✅ 稳定排序
是否自适应	✅ 对部分有序的数据效率高

---

📈 三、插入排序图解 📊

初始数组：[5, 3, 1, 4, 2]

第1轮：[3, 5, 1, 4, 2]
第2轮：[1, 3, 5, 4, 2]
第3轮：[1, 3, 4, 5, 2]
第4轮：[1, 2, 3, 4, 5]

---

🧪 四、代码实现大全 💻

我们提供以下四种实现方式：

• ✅ 静态数组（下标从 0 开始）
• ✅ 静态数组（下标从 1 开始）
• ✅ vector 容器（下标从 0 开始）
• ✅ vector 容器（下标从 1 开始）

全部使用 using namespace std;，方便理解！

---

✅ 方法一：静态数组，下标从 0 开始

#include <iostream>
using namespace std;

void insertionSort(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;
    }
}

int main() {
    int arr[] = {5, 3, 1, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "排序结果：" << endl;
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

📌 输出：

排序结果：
1 2 3 4 5

---

✅ 方法二：静态数组，下标从 1 开始（模拟 1-based 编程风格）

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 2; i <= n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 1 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }

        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {0, 5, 3, 1, 4, 2}; // 下标从 1 开始
    int n = 5; // 实际有效元素个数为 5

    insertionSort(arr, n);

    cout << "排序结果：" << endl;
    for (int i = 1; i <= n; ++i)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

📌 输出：

排序结果：
1 2 3 4 5

---

✅ 方法三：vector 容器，下标从 0 开始

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; ++i) {
        int key = nums[i];
        int j = i - 1;

        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            --j;
        }

        nums[j + 1] = key;
    }
}

int main() {
    vector<int> nums = {5, 3, 1, 4, 2};

    insertionSort(nums);

    cout << "排序结果：" << endl;
    for (int num : nums)
        cout << num << " ";
    cout << endl;

    return 0;
}

📌 输出：

排序结果：
1 2 3 4 5

---

✅ 方法四：vector 容器，下标从 1 开始（模拟 1-based）

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& nums, int n) {
    for (int i = 2; i <= n; ++i) {
        int key = nums[i];
        int j = i - 1;

        while (j >= 1 && nums[j] > key) {
            nums[j + 1] = nums[j];
            --j;
        }

        nums[j + 1] = key;
    }
}

int main() {
    vector<int> nums = {0, 5, 3, 1, 4, 2}; // nums[0] 作废
    int n = 5;

    insertionSort(nums, n);

    cout << "排序结果：" << endl;
    for (int i = 1; i <= n; ++i)
        cout << nums[i] << " ";
    cout << endl;

    return 0;
}

📌 输出：

排序结果：
1 2 3 4 5

---

🎨 五、插入排序动画演示 🎥

虽然不能在这里放动图，但你可以这样想象：

初始：[5, 3, 1, 4, 2]
→ 插入 3 → [3, 5, 1, 4, 2]
→ 插入 1 → [1, 3, 5, 4, 2]
→ 插入 4 → [1, 3, 4, 5, 2]
→ 插入 2 → [1, 2, 3, 4, 5]

---

📌 六、注意事项 ❗

注意项	说明
数组越界	特别是在下标从 1 开始时，注意不要访问 nums[0]
排序稳定性	插入排序是稳定排序
性能优化	小数据量非常高效，适合对几乎有序的数据进行排序

---

🧠 七、应用场景举例 💡

场景	示例
教学用途	学习排序基础
小数据集排序	数据量小于 100 的场景
几乎有序数据	已经大致排好序的数据
插入新元素	在已排序数组中插入一个新元素并重新排序

---

🎁 八、小彩蛋：STL 中的排序函数 🎲

虽然我们手动实现了插入排序，但在实际开发中也可以使用 STL 提供的排序函数：

#include <algorithm>
sort(arr, arr + n); // 静态数组
sort(nums.begin(), nums.end()); // vector

但这并不妨碍你学习插入排序哦！🌟

---

🏆 九、加油鼓励语 💪

👋 亲爱的同学，你已经掌握了插入排序的基本思想和多种实现方式，这是你走向算法高手的重要一步！

🎯 不管你是刚入门的小白，还是准备刷题的大神，掌握插入排序都能让你在编程世界如鱼得水！

🚀 继续加油，坚持练习，你一定能在编程路上越走越远！我们在这里为你打call！👏👏👏

---

📝 十、参考资料 & 推荐学习 🔍

资源名称	地址
C++ Reference - sort	https://cplusplus.com/reference/algorithm/sort/

---

📅 最后更新时间：2025年5月22日 22:28

🎉 祝你学得开心，编程顺利，早日成为大神！🌟