冒泡排序

场景引入

冒泡排序是最简单直观的排序算法。虽然面试中很少直接考冒泡排序本身，但它是理解比较类排序的起点，也是理解"为什么我们需要更好的排序算法"的基础。

核心思路

冒泡排序的核心是相邻元素两两比较，逆序则交换。每一轮遍历都会把当前最大的元素"冒泡"到数组末尾。

算法步骤

从数组头部开始，依次比较相邻的两个元素
如果前一个比后一个大，交换它们
一轮下来，最大的元素到达末尾
重复上述过程，每轮少比较一个元素（末尾已有序）
如果某一轮没有发生交换，说明已经有序，提前结束

算法流程图

可视化演示

加载可视化中...

代码实现

javascript

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // 优化：没有交换说明已有序
  }
  return arr;
}

优化：提前终止

注意代码中的 swapped 标志。如果某一轮内循环没有发生任何交换，说明数组已经有序，可以立即终止。这将最好情况的时间复杂度从 O(n²) 降低到 O(n)。

复杂度分析

	时间复杂度	空间复杂度
最好	O(n) — 已有序，一轮扫描	O(1)
平均	O(n²)	O(1)
最坏	O(n²) — 完全逆序	O(1)

稳定性：稳定。相等元素不会交换位置。

面试要点

冒泡排序是稳定的原地排序算法
面试中一般不会单独考冒泡排序，但会作为排序算法对比的基准
理解冒泡排序有助于理解为什么归并排序和快速排序更高效

冒泡排序 ​

场景引入 ​

核心思路 ​

算法步骤 ​

算法流程图 ​

可视化演示 ​

代码实现 ​

优化：提前终止 ​

复杂度分析 ​

面试要点 ​

相关题目 ​