illegalCreed

中文

English

中文

English

Appearance

三种算法详解与对比 ​

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

速查 ​

  • 冒泡（Bubble）：每轮从头到尾比较相邻元素，逆序就交换——一轮下来最大值「浮」到末尾；n-1 轮后有序。可加「本轮无交换则提前终止」优化，近乎有序时最好 O(n)。
  • 选择（Selection）：每轮在剩余 [i..n-1] 区找最小值的下标，与位置 i 交换（每轮至多一次交换）。共 n-1 轮，交换次数总共 O(n)，但比较次数固定 O(n²)，不稳定。
  • 插入（Insertion）：把 [0..i-1] 视为已排序区，取 a[i] 从右往左比较，比它大的逐个右移让位，找到位置插入。近乎有序时接近 O(n)，逆序最坏 O(n²)，稳定。
  • 三者本质区别：冒泡=相邻交换搬一格；选择=选最小跨距离换；插入=连续右移让位插入。冒泡/插入搬移「连续」、缓存友好；选择换「跨距离」、交换最少。
  • 比较次数：冒泡/插入 O(n²)（最好 O(n)）；选择固定 O(n²)（与有序无关）。
  • 交换次数：冒泡最坏 O(n²)、选择 O(n)、插入 O(n²)（搬移）。
  • 稳定性：冒泡稳、插入稳、选择不稳。
  • 空间：三者均 O(1)，原地。
  • 经典坑：冒泡忘加「无交换即终止」优化 → 近乎有序退化 O(n²)；选择稳定性破坏源于跨距离交换（4,4,2 → 交换 4 与 2 让两个 4 调位）；插入用 >（不是 >=）才稳定。
  • 选型：教学/稳定性 → 冒泡；交换昂贵 → 选择；小数据/近乎有序/在线 → 插入（最常用）。

一、冒泡排序：相邻比较交换 ​

思路：每轮从头到尾比较相邻两个元素，若 a[j] > a[j+1] 就交换。一轮过后，当前区间的最大值「浮」到了区间末尾。共进行 n-1 轮（每轮区间右边界减一）。

js
function bubbleSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {        // 共 n-1 轮
    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;
}
  • 为什么稳定：相邻比较，相等时 a[j] > a[j+1] 为假，不交换——相等元素的相对顺序保持不变。
  • 提前终止优化：若某一轮全程没发生交换，说明数组已有序，直接 break。这让冒泡在「已有序」输入下从 O(n²) 降到 O(n)（只跑一轮就发现没交换）。
  • 进一步优化（记录最后交换位置）：每轮记录最后一次交换的位置 lastSwap，下一轮只需扫到 lastSwap（其后已有序）——见优化与稳定性分析。
  • 缺点：交换次数最多（最坏 O(n²) 次），且每次只搬一格，是三者里实际较慢的。

二、选择排序：每轮选最小 ​

思路：维护已排序前段 [0..i-1]。每轮在剩余区 [i..n-1] 里线性扫描找最小值的下标 minIdx，然后把它与位置 i 的元素交换。共 n-1 轮。

js
function selectionSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;                         // 假设当前位置是最小
    for (let j = i + 1; j < n; j++) {       // 扫描剩余区找真正的最小
      if (a[j] < a[minIdx]) minIdx = j;     // 严格小于，保证选最靠前的最小值
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]]; // 交换（每轮至多一次）
  }
  return a;
}
  • 交换次数最少：每轮至多交换一次，n-1 轮总共 O(n) 次交换——三者中最少。适合「元素本身很大、交换昂贵」的场景（如大结构体按某 key 排序）。
  • 比较次数固定：无论输入是否有序，每轮都要把剩余区全扫一遍才能确定最小，总比较次数恒为 n(n-1)/2——无法利用初始有序性，这是它与冒泡/插入的关键差距。
  • 为什么不稳定：交换是跨距离的（把远处的最小值换到前面），可能越过相等元素。经典反例 [5a, 5b, 2]：第一轮选最小 2（下标 2）与 5a（下标 0）交换 → [2, 5b, 5a]，两个 5 的相对顺序被破坏。
  • 稳定化技巧：用「插入」代替「交换」（找到最小后整体后移一位插入），可让选择稳定，但失去「交换最少」的优势——工程上很少这么做，需要稳定就直接用插入/冒泡。

三、插入排序：插进有序区 ​

思路：把前段 [0..i-1] 视为已排序区。取 a[i]，从右往左与已排序区元素比较，比它大的逐个右移一位让位，直到找到不大于它的位置，把 a[i] 插进去。已排序区长度从 1 增长到 n。

js
function insertionSort(a) {
  const n = a.length;
  for (let i = 1; i < n; i++) {             // 从第 2 个元素开始插入
    const cur = a[i];                       // 暂存待插入元素
    let j = i - 1;
    while (j >= 0 && a[j] > cur) {          // 比它大的右移（用 > 保证稳定）
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = cur;                         // 插入到正确位置
  }
  return a;
}
  • 为什么稳定：用 a[j] > cur（严格大于），遇到相等时停下，新元素插到相等元素的右侧——相等元素的相对顺序保持不变。
  • 为什么近乎有序 O(n)：已有序时，每个 cur 只比较一次（a[j] > cur 立即假），while 不执行，总共 n-1 次比较 → O(n)。
  • 搬移连续、缓存友好：右移是连续内存操作（不像选择那样跨距离交换），实际常数比冒泡小，是三者中小数据量最快的。
  • 在线特性：来一个插一个，无需等全部元素到齐——适合流式数据（当然流式还要考虑空间，这里指算法逻辑上支持）。
  • 缺点：逆序输入最坏 O(n²)，且需大量右移；不适合大数据量。

四、三者对比表 ​

维度冒泡选择插入
比较次数（最好）O(n)（加优化）O(n²)O(n)
比较次数（平均/最坏）O(n²)O(n²)O(n²)
交换/搬移次数（最坏）O(n²)（最多）O(n)（最少）O(n²)
空间O(1)O(1)O(1)
稳定性稳定 ✅不稳定 ❌稳定 ✅
利用初始有序性能（最好 O(n)）不能能（最好 O(n)）
缓存友好好（相邻）一般（跨距离）好（连续）
工程价值教学/稳定性交换昂贵场景小数组兜底（Timsort 等）
适用场景教学、需稳定元素大、交换贵n 小、近乎有序、在线

一句话总结：冒泡最易理解且稳定；选择交换最少但不稳、不沾有序的光；插入小数据最快、稳定、沾有序的光——三者里插入的工程价值最高。

交互演示 ​

下一步 ​

理解了三种算法的代码与对比后，下一步深入冒泡的两种优化（标志位、记录最后交换位置）、选择排序不稳定的形式化证明、稳定性判定方法与插入排序的工程价值（Timsort 的 run），见优化与稳定性分析。