插入排序：插入排序如何工作？与冒泡排序对比

在编程中，排序是最基础也最常用的操作之一。无论是处理学生成绩、商品价格还是日志数据，排序都能帮我们快速整理信息。今天我们来聊聊两种简单的排序算法：插入排序和冒泡排序，看看它们是如何工作的，以及它们之间有什么区别。

插入排序：逐个“插入”的艺术¶

插入排序的核心思想非常直观，就像我们整理手中的扑克牌——从左到右逐个处理牌，将每张新牌插入到手中已有牌的正确位置。例如，我们有一副无序的牌 [5, 3, 8, 4, 2]，具体步骤如下：

1. 初始状态¶

假设手中已经有第一张牌 5（默认是“已排序部分”），剩下的牌 3, 8, 4, 2 需要插入。

2. 插入第二张牌 3¶

• 从第二张牌 3 开始，与已排序部分的最后一张牌 5 比较：3 < 5，所以需要将 5 向后移动一位，腾出位置给 3。
• 插入后，已排序部分变为 [3, 5]。

3. 插入第三张牌 8¶

• 第三张牌 8 与已排序部分的最后一张牌 5 比较：8 > 5，直接放在末尾。
• 已排序部分变为 [3, 5, 8]。

4. 插入第四张牌 4¶

• 第四张牌 4 从后往前与已排序部分的元素比较：
• 先与 8 比较：4 < 8，8 后移一位；
• 再与 5 比较：4 < 5，5 后移一位；
• 再与 3 比较：4 > 3，找到正确位置，插入后已排序部分变为 [3, 4, 5, 8]。

5. 插入第五张牌 2¶

• 第五张牌 2 从后往前与已排序部分的元素比较：
• 与 8 比较：2 < 8，8 后移；
• 与 5 比较：2 < 5，5 后移；
• 与 4 比较：2 < 4，4 后移；
• 与 3 比较：2 < 3，3 后移；
• 已到已排序部分开头，插入后整个数组变为 [2, 3, 4, 5, 8]。

算法总结：
插入排序的步骤是从第二个元素开始遍历，对每个元素 key，从当前位置往前比较，找到正确的插入位置后，将已排序部分的元素后移，最后插入 key。伪代码如下：

for i from 1 to n-1:  // 从第二个元素开始
    key = arr[i]
    j = i - 1       // 已排序部分的最后一个元素索引
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]  // 元素后移
        j = j - 1
    arr[j+1] = key  // 插入key到正确位置

冒泡排序：相邻元素的“大冒险”¶

冒泡排序的核心思想是“相邻元素比较，大的往后冒”。想象水中的气泡，最大的气泡会先浮到水面（数组末尾），然后次大的气泡再浮上来，直到所有气泡排好序。

冒泡排序示例（以数组 [5, 3, 8, 4, 2] 为例）¶

• 第一轮：从第一个元素开始，相邻比较，将大元素“冒泡”到末尾：
• 5 和 3 比较：5 > 3，交换 → [3, 5, 8, 4, 2]；
• 5 和 8 比较：5 < 8，不交换；
• 8 和 4 比较：8 > 4，交换 → [3, 5, 4, 8, 2]；

• 8 和 2 比较：8 > 2，交换 → [3, 5, 4, 2, 8]。
  第一轮结束，最大的 8 已“冒泡”到末尾。

• 第二轮：处理前4个元素（排除最后一个 8）：

• 3 和 5 比较：不交换；
• 5 和 4 比较：5 > 4，交换 → [3, 4, 5, 2, 8]；

• 5 和 2 比较：交换 → [3, 4, 2, 5, 8]。
  第二轮结束，第二大的 5 到了倒数第二位。

• 第三轮：处理前3个元素（排除最后两个）：

• 3 和 4 比较：不交换；

• 4 和 2 比较：交换 → [3, 2, 4, 5, 8]。
  第三轮结束，第三大的 4 到了倒数第三位。

• 第四轮：处理前2个元素（排除最后三个）：

• 3 和 2 比较：交换 → [2, 3, 4, 5, 8]。
  第四轮结束，整个数组排好序。

算法总结：
冒泡排序需要 n-1 轮（n 为数组长度），每轮比较相邻元素，将大元素后移。每轮结束后，未排序部分会少一个元素。

插入排序 vs 冒泡排序：谁更优？¶

总结¶

插入排序和冒泡排序都是简单的 O(n²) 排序算法，但插入排序在实际应用中更高效，尤其是数据接近有序时。冒泡排序虽然直观，但移动元素的次数更多（每次比较都可能交换），而插入排序只需在确定位置后移动元素，交换次数更少。

对于初学者来说，理解这两种排序的核心思想（插入 vs 冒泡）是掌握更复杂排序算法（如快速排序、归并排序）的基础。