JavaScript冒泡排序代码实现与逻辑详解

冒泡排序（Bubble Sort）是一种基于比较和元素交换的原地排序算法。它的核心运作方式是：重复遍历待排序的数组，依次比较相邻的两个元素，如果它们的次序与目标规则相反就交换两者的位置。每次遍历结束后，未排序区域中的最大（或最小）元素都会像水底的气泡一样逐步浮动到序列的末尾。在 JavaScript 开发中，尽管生产环境普遍使用引擎内置的高性能 Array.prototype.sort()，但深入理解冒泡排序的双重循环控制、状态标志位判断以及区间收缩机制，是建立算法时间与空间复杂度认知、掌握代码边界控制的经典范例。

一、冒泡排序的核心原理与多轮冒泡推导

为了直观建立直觉，以升序排序数组 [5, 2, 8, 4, 1] 为例。数组长度为 5，排序过程需要进行多轮比较：

• 第 1 轮遍历：指针从索引 0 开始向右移动。首先比较 5 与 2，因为 5 > 2，交换位置变为 [2, 5, 8, 4, 1]；接着比较 5 与 8，符合顺序不交换；比较 8 与 4，发生交换变为 [2, 5, 4, 8, 1]；最后比较 8 与 1，交换后变为 [2, 5, 4, 1, 8]。至此，全数组最大的元素 8 已经沉淀在最右端（索引 4），不再参与后续比较。
• 第 2 轮遍历：对前 4 个元素重复相同过程。依次比对 [2, 5, 4, 1]，5 会逐步被推向索引 3 的位置，数组状态变为 [2, 4, 1, 5, 8]。
• 后续各轮：以此类推，每走完一轮，右侧有序区的元素就增加 1 个，左侧未排序区的元素对应减少 1 个。对于长度为 \(n\) 的数组，最多只需进行 \(n - 1\) 轮冒泡，即可保证整体有序。

二、基础版本的 JavaScript 代码实现

实现冒泡排序的核心在于使用双重 for 循环：外层循环控制遍历轮数，内层循环负责在未排序区域内进行两两比对与交换。为了避免破坏调用方传入的原始数组，推荐在函数开头通过展开运算符 [...arr] 复制原数组。

/**
 * 基础冒泡排序实现
 * @param {number[]} arr - 输入数组
 * @returns {number[]} 排序后的新数组
 */
function bubbleSortBasic(arr) {
  // 边界保护：若传入空或单元素数组直接返回副本
  if (!Array.isArray(arr) || arr.length <= 1) {
    return Array.isArray(arr) ? [...arr] : [];
  }

  const result = [...arr];
  const len = result.length;

  // 外层循环：共执行 len - 1 轮
  for (let i = 0; i < len - 1; i++) {
    // 内层循环：逐对比较相邻元素
    // 注意：减去 i 是因为末尾的 i 个元素已经是有序的
    for (let j = 0; j < len - 1 - i; j++) {
      if (result[j] > result[j + 1]) {
        // 使用 ES6 解构赋值完成原地交换
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
      }
    }
  }

  return result;
}

// 示例运行
const sampleData = [5, 2, 8, 4, 1];
console.log('排序结果:', bubbleSortBasic(sampleData));
// 控制台输出示例: 排序结果: [1, 2, 4, 5, 8]

三、单步交换操作与执行执行流拆解

为了清晰把握程序在单次循环内部的执行细节，我们可以将内层循环的每一步拆解为三个动作：比对、条件判断、解构互换。图 2 详细分解了单次相邻元素判别与数据交换的数据流转过程：

四、两项关键优化：标志位提前退出与记录最后交换位置

基础版本的冒泡排序存在一个显著的性能缺陷：即使数组在某一轮遍历后已经完全有序，或者输入本身就是已排序数组（例如 [1, 2, 3, 4, 5]），外层循环仍然会盲目执行完剩余的全部轮次，时间复杂度始终锁定在 \(O(n^2)\)。针对这一问题，有两种行之有效的优化方案：

1. 标志位优化（Early Exit）

在外层循环内设置布尔标志变量 hasSwapped = false。如果某轮内层遍历发生任何一次交换，将其置为 true。当某一整轮比对结束后，若 hasSwapped 依然为 false，表明序列已达到全局有序，立刻跳出循环。在最佳输入（完全升序）情况下，算法耗时降低至 \(O(n)\)。

2. 记录最后交换边界优化

如果数组末尾已经有较多元素排好序，单靠 len - 1 - i 缩减范围依然不够激进。通过在内层循环记录“最后一次发生交换的位置” lastSwapIndex，下一轮外层遍历只需将比对上限设定为该索引位置即可，大幅跳过了已然有序的后缀片段。

优化版完整代码实现

/**
 * 高性能优化版冒泡排序
 * 结合标志位提前终止与最后交换边界收缩
 * @param {number[]} arr - 输入数组
 * @returns {number[]} 排序后的新数组
 */
function bubbleSortOptimized(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) {
    return Array.isArray(arr) ? [...arr] : [];
  }

  const result = [...arr];
  // sortBorder 代表右侧无序区域的截止索引
  let sortBorder = result.length - 1;

  while (sortBorder > 0) {
    let lastExchangeIndex = 0;
    let hasSwapped = false;

    // 仅比较至上次记录的交换边界
    for (let j = 0; j < sortBorder; j++) {
      if (result[j] > result[j + 1]) {
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
        hasSwapped = true;
        lastExchangeIndex = j; // 记录最后一次发生交换的位置
      }
    }

    // 若整轮均无交换，说明已经全局有序，直接退出
    if (!hasSwapped) {
      break;
    }

    // 缩减下一轮的比较边界至最后一次交换点
    sortBorder = lastExchangeIndex;
  }

  return result;
}

// 示例运行
const nearlySorted = [2, 1, 3, 4, 5, 6, 7];
console.log('优化版输出:', bubbleSortOptimized(nearlySorted));
// 控制台输出示例: 优化版输出: [1, 2, 3, 4, 5, 6, 7]

五、算法复杂度与适用边界总结

冒泡排序的理论模型和实际工程性能表现如下：

• 时间复杂度：
  • 最好情况 \(O(n)\)：优化版本在遇到原本完全有序的数据时，只需完成首轮 \(n - 1\) 次比对，触发 hasSwapped === false 退出。
  • 最坏情况 \(O(n^2)\)：当输入数组严格降序时，每一对相邻元素都需要交换，总比较次数为 \(n(n - 1) / 2\)。
  • 平均情况 \(O(n^2)\)：对于随机乱序输入，平均逆序对数量约为 \(n(n - 1) / 4\)，因此平均复杂度依然是平方级别。
• 空间复杂度 \(O(1)\)：算法在原数组上直接进行变量交换（In-place 原地排序），仅需常数级别的辅助变量存储指针和标志位。
• 稳定性：稳定。只有当 arr[j] > arr[j+1] 严格成立时才会发生位置交换，相等的两个元素相对位置不会发生改变。

六、常见问题与注意事项

• 稳定性破坏问题：在写比较条件时，必须使用严格大于 arr[j] > arr[j + 1]。若错误写成 arr[j] >= arr[j + 1]，相等的元素在相邻时也会被强行调换位置，从而破坏算法的稳定性。
• 原数组变异（Mutation）：在 JavaScript 中对象和数组是通过引用传递的。如果不做浅拷贝直接在原数组上解构互换，将永久改动函数外部传入的原始数据。对外公开的纯函数工具应当优先维护不可变性。
• 大数据量性能瓶颈：当数据规模达到上万条时，平方级别复杂度的算法耗时将呈指数级激增，严重阻塞浏览器的主渲染线程导致界面假死。因此在面对高并发、大数据排序需求时，应使用快速排序、归并排序或内置方法。