js实现冒泡算法

冒泡排序算法原理

冒泡排序是一种简单的排序算法，通过重复遍历待排序的列表，比较相邻元素并交换位置，将较大的元素逐渐“冒泡”到列表末尾。

JavaScript实现代码

function bubbleSort(arr) {
  let 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) {
  let 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;
}

算法复杂度分析

• 时间复杂度：

  • 最优情况（已排序）：O(n)
  • 最差情况（逆序）：O(n²)
  • 平均情况：O(n²)

• 空间复杂度：O(1)，属于原地排序算法

  

使用示例

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