用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;
}

使用示例

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

时间复杂度分析

冒泡排序的最坏和平均时间复杂度都是 O(n²)，最好情况（数组已经有序）下优化后的版本可以达到 O(n)。空间复杂度为 O(1)，因为排序是原地进行的。