js实现冒泡算法

冒泡排序算法原理

冒泡排序是一种简单的排序算法，通过重复遍历待排序的列表，比较相邻元素并交换位置，使得较大的元素逐渐“冒泡”到列表的末尾。每次遍历都会将当前未排序部分的最大元素移动到正确位置。

JavaScript实现代码

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    // 标志位，用于优化
    let swapped = false;
    for (let j = 0; j < len - 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;
}

代码说明

• 外层循环控制遍历的轮数，共需进行n-1轮比较（n为数组长度）。
• 内层循环进行相邻元素的比较和交换，每轮结束后，最大的元素会移动到数组末尾。
• swapped标志位用于优化算法，当某一轮没有发生交换时，说明数组已有序，可提前终止排序。

时间复杂度分析

• 最坏情况下（逆序数组），时间复杂度为$O(n^2)$。
• 最好情况下（已排序数组），优化后的时间复杂度为$O(n)$。
• 平均时间复杂度为$O(n^2)$。

使用示例

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(unsortedArray)); 
// 输出: [11, 12, 22, 25, 34, 64, 90]