# 冒泡排序

# 算法原理

冒泡排序是一种简单的排序算法，它重复地遍历要排序的序列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个过程会重复进行，直到没有再需要交换的元素，也就是说该序列已经排序完成。

算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端（升序排列），就如同水中的气泡最终会上浮到顶端一样。

# 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换它们两个
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
针对所有的元素重复以上的步骤，除了最后一个
重复步骤1~3，直到没有任何一对数字需要比较

# 动图演示

比较次数: 0

交换次数: 0

# 代码实现

function bubbleSort(arr) {
  const len = arr.length;
  
  for (let i = 0; i < len; i++) {
    // 每次循环后，最大的元素会被放到正确的位置
    // 所以下一次循环就可以少比较一个元素
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换元素
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  
  return arr;
}

# 复杂度分析

# 时间复杂度

最好情况：O(n)，当数组已经有序时
最坏情况：O(n²)，当数组逆序时
平均情况：O(n²)

# 空间复杂度

O(1)，只需要一个临时变量用于交换

# 算法特点

# 优点

实现简单，容易理解
稳定排序
原地排序，不需要额外空间

# 缺点

时间复杂度较高，对于大规模数据效率较低
交换次数较多

# 适用场景

小规模数据排序
数据基本有序的情况
作为教学或理解排序算法的入门示例

# 优化方案

设置标志位，记录每轮是否发生交换，如果没有交换说明已经有序，可以提前退出
记录最后一次交换的位置，下一轮扫描到该位置即可

function optimizedBubbleSort(arr) {
  const len = arr.length;
  let lastSwap = len - 1;
  let swapPos = 0;
  
  for (let i = 0; i < len; i++) {
    let swapped = false;
    
    for (let j = 0; j < lastSwap; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
        swapPos = j;
      }
    }
    
    // 更新下一轮扫描的终点
    lastSwap = swapPos;
    
    // 如果没有发生交换，说明已经有序
    if (!swapped) break;
  }
  
  return arr;
}

← 排序算法选择排序 →