js实现冒泡

实现冒泡排序的JavaScript代码

冒泡排序是一种简单的排序算法，通过重复遍历待排序列表，比较相邻元素并交换位置，使得较大（或较小）的元素逐渐“浮”到列表的顶端。

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换元素
      }
    }
  }
  return arr;
}

优化后的冒泡排序

在基础版本上增加标志位，当某一轮遍历没有发生交换时，说明数组已有序，可以提前终止排序。

function optimizedBubbleSort(arr) {
  const n = arr.length;
  let swapped;
  for (let i = 0; i < n - 1; i++) {
    swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // 没有交换则提前退出
  }
  return arr;
}

使用示例

const array = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort([...array])); // [11, 12, 22, 25, 34, 64, 90]
console.log(optimizedBubbleSort([...array])); // 同上

算法特性

• 时间复杂度：最坏情况O(n²)，最好情况（优化后）O(n)
• 空间复杂度：O(1)，属于原地排序
• 稳定性：是稳定排序（相等元素不会改变相对位置）

可视化理解

冒泡排序的每一轮会将当前未排序部分的最大值“冒泡”到正确位置。例如数组[5,3,8,4,2]的排序过程：

1. 第一轮后：[3,5,4,2,8]（8到位）
2. 第二轮后：[3,4,2,5,8]（5到位）
3. 第三轮后：[3,2,4,5,8]（4到位）
4. 第四轮后：[2,3,4,5,8]（完成排序）