插入排序 Insertion Sort

一种简单直观的基础排序算法，如同整理手中的扑克牌。

基本思想

插入排序的工作方式是：构建最终排序好的序列，一次一个元素。它迭代地从未排序的部分取出一个元素，并将其插入到已排序部分的正确位置。

想象一下你正在玩扑克牌，拿到新牌时，你会从右到左（或从左到右）比较，找到合适的位置插入，使得手中的牌始终保持有序。

5 ♠

Q ♥

8 ♥

3 ♣

A ♦

已排序手牌区

3 ♣

5 ♠

8 ♥

Q ♥

A ♦

插入排序流程演示

通过下面的动画，观察插入排序如何逐步将元素插入到已排序的部分。数组元素由柱状图表示，高度代表其值。

点击“下一步”或“自动播放”开始。初始数组已生成。

C++ 代码实现

这是插入排序的核心 C++ 实现。代码简洁地体现了其“查找并插入”的逻辑。

void insertionSort(int a[], int n) {
    // 从第二个元素开始 (索引为1)
    for (int i = 1; i < n; i++) {
        int key = a[i]; // 当前待插入的元素
        int j = i - 1;  // 指向已排序部分的末尾

        // 在已排序部分从后往前找插入位置
        // 将比 key 大的元素向后移动
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]; // 元素右移
            j--;             // 继续向前比较
        }
        // 找到合适位置 (a[j] <= key 或 j < 0)
        a[j + 1] = key; // 插入 key
    }
}

代码逻辑解析

外层循环 (for i = 1 to n-1): 遍历未排序部分的每个元素 `a[i]`。`i` 是当前待插入元素的索引。
保存关键字 (key = a[i]): 将待插入的元素 `a[i]` 暂存到 `key` 变量中。
内层循环 (while j >= 0 and a[j] > key):
- `j = i - 1` 初始化为已排序区域的最后一个元素的索引。
- 循环条件：只要 `j` 没有越界（`>= 0`），并且已排序区域的当前元素 `a[j]` 大于 `key`。
- 元素右移 (a[j + 1] = a[j]): 将大于 `key` 的元素 `a[j]` 向右移动一个位置，为 `key` 腾出空间。
- 指针左移 (j--): 继续与前一个已排序元素比较。
插入关键字 (a[j + 1] = key): 当 `while` 循环结束时，`j + 1` 就是 `key` 应该插入的位置（要么是 `a[j]` 不再大于 `key`，要么是 `j` 已经小于 0，表示 `key` 应该放在最前面）。

复杂度与特性分析

了解算法的效率对于选择合适的排序方法至关重要。插入排序在不同情况下的表现差异较大。

场景	时间复杂度 (比较次数)	时间复杂度 (移动次数)	空间复杂度
最好情况 (数组已排序)	O(n)	O(1) - 无需移动	O(1)
最坏情况 (数组逆序)	O(n²)	O(n²)	O(1)
平均情况	O(n²)	O(n²)	O(1)

优点

实现简单，易于理解。
对于小规模数据集或基本有序的数据集非常高效 (接近 O(n))。
稳定排序： 相等元素的相对顺序不会改变。
原地排序，空间复杂度低 (O(1))。
在线算法：可以边接收数据边排序。

缺点

对于大规模或随机数据集，效率较低 (O(n²))。
比较次数和移动次数较多。

稳定性说明

稳定性指：如果数组中有两个相等的元素，排序后它们的相对位置保持不变。

插入排序是稳定的。因为在 `while (j >= 0 && a[j] > key)` 条件中，只有当 `a[j]` 严格大于 `key` 时才会移动。如果 `a[j] == key`，循环会停止，`key` 会被插入到 `a[j]` 的后面，保持了相等元素的原始顺序。

与其他基础排序对比

插入排序通常与选择排序、冒泡排序一起作为入门级排序算法进行比较。

插入排序

核心思想: 将元素插入已排序序列
时间复杂度: O(n) ~ O(n²)
空间复杂度: O(1)
稳定性: 稳定
优势: 对近乎有序数据高效

详细说明

插入排序像整理扑克牌，不断将新牌插入到手中已排好序的牌里。对于小数组或基本有序的数组，它的表现非常好，甚至优于 O(n log n) 的算法。原地排序且稳定是其重要特性。

选择排序

核心思想: 每次选最小/大元素
时间复杂度: O(n²) (稳定)
空间复杂度: O(1)
稳定性: 不稳定
优势: 移动次数少 (O(n))

详细说明

选择排序每次从未排序部分找到最小（或最大）的元素，放到已排序部分的末尾。它的比较次数总是 O(n²)，但交换次数是 O(n)，这在元素交换成本很高时有优势。但它通常是不稳定的。

冒泡排序

核心思想: 相邻元素比较交换
时间复杂度: O(n) ~ O(n²)
空间复杂度: O(1)
稳定性: 稳定
优势: 易于理解，可提前终止

详细说明

冒泡排序重复地遍历列表，比较相邻元素，如果顺序错误就交换它们。每一轮遍历至少将一个最大（或最小）元素“冒泡”到最终位置。可以优化，若一轮没有发生交换则表示已排序。是稳定的算法。

知识测验

检验一下你对插入排序的理解程度吧！

进度: 0 / 5

正在加载测验...

编程练习

实践是检验真理的唯一标准。尝试实现下面的插入排序相关问题。

练习 1: 基本插入排序

编写一个 C++ 函数 `insertionSortInt(int arr[], int n)`，接收一个整型数组 `arr` 和其大小 `n`，使用插入排序将其升序排列。你可以在下面的编辑器中编写和测试你的代码（注意：此编辑器仅供练习，无实际编译运行功能）。

练习 1 编辑区

练习 2: 改进与统计

修改插入排序算法，编写一个 C++ 函数 `insertionSortFloat(float arr[], int n, long long& comparisonCount)`，使其能够对浮点数数组进行排序，并统计在排序过程中执行的比较次数（即 `a[j] > key` 的判断次数）。比较次数通过引用参数 `comparisonCount` 返回。

练习 2 编辑区

// 在这里编写你的 C++ 代码
#include <iostream>
using namespace std;

// 请在此处实现 insertionSortFloat 函数
void insertionSortFloat(float arr[], int n, long long& comparisonCount) {
    comparisonCount = 0; // 初始化比较次数
    for (int i = 1; i < n; ++i) {
        float key = arr[i];
        int j = i - 1;
        // 注意: 每次进入while循环判断 a[j] > key 就算一次比较
        // 即使j<0，while条件判断本身也涉及比较逻辑启动，但通常我们只计成功进入循环体的比较
        // 或者更精确地，计 a[j] > key 的执行次数
        while (j >= 0) {
             comparisonCount++; // 统计比较次数
             if (arr[j] > key) {
                 arr[j + 1] = arr[j];
                 j--;
             } else {
                 break; // 找到位置，跳出内层while
             }
        }
        // 另一种统计方式：仅在 arr[j] > key 成立时计数
        /*
        while (j >= 0 && arr[j] > key) {
            comparisonCount++; // 在这里计数更符合 "a[j] > key" 的判断次数
            arr[j + 1] = arr[j];
            j--;
        }
        if (j >= 0) { // 如果循环不是因为 j < 0 结束，说明 arr[j] <= key 发生了最后一次比较
             comparisonCount++; // 补上最后一次失败的比较
        }
        */

arr[j + 1] = key;
    }
}

// --- 测试代码 (仅供参考) ---
// void printFloatArray(float arr[], int n) {
//     for(int i = 0; i < n; ++i) { cout << arr[i] << " "; }
//     cout << endl;
// }
// int main() {
//     float data[] = {3.14f, 1.618f, 2.718f, 0.577f, 1.414f};
//     int n = sizeof(data)/sizeof(data[0]);
//     long long comparisons = 0;
//     cout << "原始数组: ";
//     printFloatArray(data, n);
//     insertionSortFloat(data, n, comparisons);
//     cout << "排序后数组: ";
//     printFloatArray(data, n);
//     cout << "比较次数: " << comparisons << endl;
//     return 0;
// }

总结与展望

你已经系统学习了插入排序的核心知识！

插入排序适用场景总结

✅ **小型数据集：** 当 n 较小时，其 O(n²) 复杂度影响不大，简单性反而成为优势。
✅ **基本有序的数据集：** 效率接近 O(n)，非常高效。
✅ **需要稳定排序：** 保持相等元素的原始顺序。
✅ **内存受限环境：** O(1) 的空间复杂度非常友好。
✅ **在线处理：** 可以逐步构建排序序列。

性能对比概览

相比选择排序和冒泡排序，插入排序在平均情况和最好情况下的性能通常更好（尤其对近乎有序数据）。但在最坏情况下，三者都是 O(n²)。

"就像把牌一张张插入手牌..."

(已排序手牌)

? ♠

? ♥

? ♣

延伸学习

插入排序是基础，了解它有助于理解更高级的排序算法。接下来可以探索：

希尔排序 (Shell Sort): 插入排序的改进版，处理更大间隔的元素，提高效率。
归并排序 (Merge Sort): 基于分治思想，稳定且时间复杂度为 O(n log n)。
快速排序 (Quick Sort): 同样基于分治，平均 O(n log n)，但最坏 O(n²)，通常比归并快，但不稳定。
堆排序 (Heap Sort): 利用堆数据结构，O(n log n)，原地排序但不稳定。