冒泡排序

场景引入

冒泡排序是最简单直观的排序算法。它是理解比较类排序的起点，也是理解"为什么我们需要更好的排序算法"的基础。

核心思路

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

算法步骤

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

算法流程图

可视化演示

加载可视化中...

代码实现

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)。

逆序度：冒泡排序的交换次数本质

理解冒泡排序的性能，关键在于理解逆序度这个概念。

有序度与逆序度

对于数组 [3, 8, 2, 1, 5]，我们列出所有有序对（a[i] < a[j] 且 i < j）：

(3,8)  (3,5)
(8,5) — 无，8 > 5
(2,5)
(1,5)
→ 有序对：(3,8), (3,5), (2,5), (1,5) = 4 个

满有序度：数组完全升序时的有序对数量 = n×(n-1)/2
逆序度 = 满有序度 - 有序度

交换次数 = 逆序度

冒泡排序每次交换只交换相邻元素，每交换一次恰好消除一个逆序对。因此：

冒泡排序的交换次数恒等于初始数组的逆序度。

这意味着冒泡排序的平均交换次数 = n×(n-1)/4（随机排列的期望逆序度）。

实测验证

数组大小

数据分布

点击「运行测试」，在你的浏览器中实时运行排序算法，统计比较和交换次数。

试试切换「已排序」和「逆序」数据——已排序时交换次数为 0（逆序度 = 0），完全逆序时交换次数最大 = n×(n-1)/2（逆序度 = 满有序度）。

复杂度分析

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

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

原地排序：是。只需要常数级额外空间。

深入理解

冒泡排序是稳定的原地排序算法
交换次数 = 逆序度，理解这一点就能直观判断冒泡在不同数据分布下的表现
冒泡排序通常作为排序算法对比的基准，理解它的局限有助于理解为什么归并排序和快速排序更高效

冒泡排序 ​

场景引入 ​

核心思路 ​

算法步骤 ​

算法流程图 ​

可视化演示 ​

代码实现 ​

优化：提前终止 ​

逆序度：冒泡排序的交换次数本质 ​

有序度与逆序度 ​

交换次数 = 逆序度 ​

实测验证 ​

复杂度分析 ​

深入理解 ​

相关题目 ​