illegalCreed

中文

English

中文

English

Appearance

优化与稳定性分析 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 冒泡优化①标志位：每轮用一个 swapped 标志，本轮无交换说明已有序，break 提前终止——已有序输入从 O(n²) 降到 O(n)。
  • 冒泡优化②记录最后交换位置：每轮记最后一次交换的位置 lastSwap，下一轮只需扫到 lastSwap（其后已有序），减少无效比较。
  • 选择排序为何不稳定：跨距离交换——把远处的最小值换到位置 i，会越过中间的相等元素。反例 [5a, 5b, 2] → 交换 2 与 5a 得 [2, 5b, 5a]，两个 5 调位。
  • 稳定性正式定义：排序后，值相等的元素仍保持原序列中的相对顺序，则稳定；否则不稳定。
  • 稳定性判定口诀：「只比较/交换相邻」且「相等不动」→ 稳定；「跨距离交换」→ 可能不稳（选择、快排、堆排都属于此类）。
  • 插入排序的工程价值：n 小（≤32~64）或近乎有序时比 O(n log n) 还快——Java Arrays.sort、Python Timsort、V8 Array.sort 在小数据段都退化为插入排序。
  • Timsort 的 run：Timsort 先把数组切成「已有序段（run）」，长度不足时用插入排序补齐到 minrun（通常 32~64），再归并——插入排序是小段「找有序」的主力。
  • 何时用插入排序：n ≤ 几十、或数据近乎有序、或在线插入场景；逆序大数据则别用。
  • 稳定性何时有用：待排序记录有多个 key 时（如先按 A 排，再按 B 排，希望 A 相同者内 B 序不被破坏），必须用稳定排序。
  • 一句话：冒泡两种优化让它「沾有序的光」；选择不沾光且不稳；插入沾光且稳定——这就是插入活下来的原因。

一、冒泡排序的两种优化 ​

优化①：标志位提前终止 ​

朴素冒泡即使输入已有序，仍要跑满 n-1 轮。加一个 swapped 标志：若某一轮全程没交换，说明数组已有序，提前终止。

js
function bubbleSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;           // 本轮无交换 → 已有序
  }
  return a;
}

效果：已有序输入只跑一轮就发现无交换，复杂度从 O(n²) 降到 O(n)。这是冒泡「最好 O(n)」的来源。

优化②：记录最后交换位置 ​

更精细的观察：每轮最后一次交换位置 lastSwap 之后的元素，其实已经有序了（否则还会交换）。下一轮的内层循环只需扫到 lastSwap 即可，不必扫到 n-1-i。

js
function bubbleSort(a) {
  const n = a.length;
  let end = n - 1;                 // 当前轮内层循环的右边界
  while (end > 0) {
    let lastSwap = 0;              // 本轮最后交换位置
    for (let j = 0; j < end; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        lastSwap = j;              // 更新最后交换位置
      }
    }
    end = lastSwap;                // 下一轮只需扫到这里（其后已有序）
  }
  return a;
}

效果：对「部分有序」的输入（如 [1,2,4,3,5,6,7]，只有中段无序），能大幅减少无效比较。优化①是优化②的特例（lastSwap=0 即整体有序）。

二、选择排序为何不稳定 ​

选择排序的「每轮把最小值换到前段」是跨距离交换——这是它不稳定的根源。

形式化反例：对 [5a, 5b, 2]（5a、5b 值都为 5，下标区分先后）做选择排序：

  1. 第 1 轮：在 [5a, 5b, 2] 中找最小，得 2（下标 2），与位置 0 的 5a 交换 → [2, 5b, 5a]。
  2. 第 2 轮：在 [5b, 5a] 中找最小，得 5b（下标 1），位置 1 就是最小，不交换 → [2, 5b, 5a]。

结果 [2, 5b, 5a]——两个 5 的相对顺序从 5a 在 5b 前 变成了 5b 在 5a 前，稳定性被破坏。

根因：位置 0 的 5a 被远处的 2 顶替，而 5a 被换到了原本 2 的位置（下标 2），越过了一起排在前段的 5b。任何「把远处元素换到当前位置」的操作都可能越过相等元素——这是跨距离交换的通病（快排、堆排的不稳定也源于此）。

对比：冒泡/插入只比较相邻或连续右移，相等元素之间不会发生「越过」，所以稳定。这就是稳定性判定口诀的依据：

只比较/交换相邻 + 相等不动 → 稳定；跨距离交换 → 可能不稳。

能稳定化吗：可以——用「插入」代替「交换」（找到最小后，把 a[i..minIdx-1] 整体右移一位，再把最小插入位置 i），这样最小值的搬移变成连续的，稳定。但失去「交换最少」的优势，工程上需要稳定就直接用插入/冒泡，很少这么做。

三、稳定性的正式定义与判定 ​

正式定义：设原序列中 a[i] == a[j] 且 i < j（即 a[i] 在 a[j] 前）。若排序后 a[i] 仍在 a[j] 前，则该排序稳定；否则不稳定。

稳定性何时有意义：仅当「待排序记录含多个相同 key」时才有意义——所有 key 都互不相同时，稳不稳都一样。

判定口诀与常见算法：

算法稳定？判定依据
冒泡稳定 ✅相邻交换，相等不动（用 >）
插入稳定 ✅连续右移，相等停下插右侧（用 >）
选择不稳定 ❌跨距离交换越过相等元素
归并稳定 ✅merge 时相等取左边（保证稳定）
快排不稳定 ❌划分是跨距离交换
堆排不稳定 ❌堆调整跨距离搬移

稳定性何时有用：多 key 排序。例如员工表先按部门排序，再按工龄排序——若第二次排序不稳，同部门内工龄序会被打乱。这时第二次（决定主序的）必须用稳定排序。这是「稳定」真正的工程价值，而非理论洁癖。

四、插入排序的工程价值 ​

插入排序并非「玩具」——它活在所有现代排序的小数组分支里：

  • Java Arrays.sort(int[])：双轴快排（Dual-Pivot Quicksort），但 n < 47 时切回插入排序。
  • Python list.sort / sorted：Timsort，每个 run 长度不足 minrun（典型 32~64）时用插入排序补齐。
  • V8 Array.sort：Timsort，小数组（≤32 左右）用成对插入排序（pair insertion sort）。

为什么小数组插入更快：O(n log n) 排序有递归调用、分治、辅助数组等常数开销，n 小时这些开销超过 O(n²) 的简单扫描；插入排序常数极小（内层就一个 while 循环 + 连续右移），n ≤ 几十时反而赢。

Timsort 的 run：插入排序做「找有序」主力 ​

Timsort 的核心是利用「真实数据常含已有序段」。它先把数组切成若干 run（严格升序或非严格降序的连续段）：

  • 扫描天然 run；若长度不足 minrun（由 n 算出，典型 32~64），用插入排序补齐到 minrun。
  • 然后用类似归并的方式，在 run 间做稳定归并。

这里插入排序的作用是「把零碎的短段快速整成有序的 minrun」——因为 minrun 很小，插入排序刚好最快。理解了这一点，就理解了「插入排序是 Timsort 的零件」。

五、何时该用插入排序 ​

场景是否用插入排序理由
n ≤ 几十（小数据）✅ 推荐常数最小，比快排/归并快
数据近乎有序✅ 推荐最好 O(n)
在线/流式（来一个排一个）✅ 合适算法逻辑支持增量插入
大数据、逆序、无序❌ 别用退化 O(n²)
需稳定 + 元素交换昂贵⚠️ 可选插入搬移多；选择交换少但不稳，权衡

实战口诀：n 小或近有序 → 插入；大数据 → 上 O(n log n)（快排/归并/堆排）；多 key 要稳 → 归并/Timsort。

交互演示 ​

下一步 ​

掌握了优化与稳定性分析后，若要查复杂度表、代码模板、对比矩阵与易错点，见参考；若要进入 O(n log n) 排序，可继续后续章节（归并/快排/堆排）。