插入排序：从扑克牌理牌说起，轻松掌握经典排序算法（含进阶优化与稳定性分析）

插入排序：从扑克牌理牌说起，轻松掌握经典排序算法（含进阶优化与稳定性分析）

“简单却优雅，稳定又实用”——插入排序的魅力

大家好！今天我们深入聊聊数据结构中一个既基础又实用的排序算法——插入排序（Insertion Sort）。无论你是刚接触编程的新手，还是正在准备面试的求职者，理解插入排序都大有裨益。

🃏 从理扑克牌说起

想象一下，你手里拿着一摞打乱的扑克牌，要按从小到大的顺序整理。你会怎么做？

通常，我们会：

这，就是插入排序的思想！

🔢 插入排序全过程演示（附例子）

我们以数组 arr = [5, 2, 4, 6, 1, 3] 为例，一步步看插入排序如何工作：

步骤

当前数组状态

说明

✅ 每一步都保证左侧是有序的，最终整个数组有序！

💻 C语言实现（标准版）

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i – 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j–;
        }
        arr[j + 1] = key;
    }
}

⚡ 优化版：折半插入排序（Binary Insertion Sort）

在标准插入排序中，我们通过线性扫描找插入位置，时间复杂度为 O(n)。但既然“已排序区”是有序的，为何不用二分查找来加速定位？

这就是折半插入排序的核心思想！

✅ 优点：

• 减少比较次数（从 O(n) 降到 O(log n)）

• 移动元素次数不变（仍需 O(n) 时间移动）

💻 C语言实现（折半版）：

#include <stdio.h>

void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int left = 0, right = i;

        // 二分查找插入位置
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] > key)
                right = mid;
            else
                left = mid + 1;
        }

        // 将 arr[left..i-1] 后移一位
        for (int j = i; j > left; j–) {
            arr[j] = arr[j – 1];
        }
        arr[left] = key;
    }
}

📌 注意：虽然比较次数减少，但整体时间复杂度仍是 O(n²) ，因为元素移动仍需线性时间。但在实际运行中，尤其当比较操作代价高时，折半插入排序会更快。

🧪 算法稳定性详解（附实例）

什么是稳定性？
如果排序后，相等元素的相对顺序没有改变，则称该排序算法是稳定的。

✅ 插入排序是稳定的！

举个例子：

假设我们对以下带“颜色标签”的数组排序（数字相同但来源不同）：

原始数组（格式：值/标签）：
[ (3,红), (1,蓝), (3,绿), (2,黄) ]

我们只按数值排序，不考虑标签。

使用插入排序过程如下：

✅ 可见，两个 3 的相对顺序（红→绿）没有改变，因此插入排序是稳定的！

🔍 关键点：代码中判断条件是 arr[j] > key，**不是 >=**。若写成 >=，就会破坏稳定性！

📊 性能总结

特性

标准插入排序

折半插入排序

✅ 小结

插入排序虽简单，却蕴含深刻思想：

• 直观如理牌，易于理解和实现；

• 稳定可靠，适合对相等元素有顺序要求的场景；

• 可优化，通过二分查找提升效率；

• 是高级算法的基石（如希尔排序、Timsort 的底层组件）。

“看似平凡的算法，往往藏着不平凡的智慧。”

如果你觉得这篇文章有帮助，欢迎点赞、在看、转发给更多朋友！
也欢迎在评论区留言：你在项目中用过插入排序吗？或者你还想了解哪些排序算法？