js冒泡实现

冒泡排序实现

冒泡排序是一种简单的排序算法，通过重复地遍历要排序的数列，比较相邻的元素并交换它们的位置，使得较大的元素逐渐“浮”到数列的末端。

基本实现步骤

1. 外层循环控制遍历的轮数，每一轮会将当前未排序部分的最大元素移动到正确位置。
2. 内层循环负责比较相邻元素，如果前一个元素比后一个元素大，则交换它们的位置。
3. 每一轮遍历后，最大的元素会被移动到数组末尾，因此下一轮遍历可以减少一个元素的比较。

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

时间复杂度分析

• 最坏情况时间复杂度：O(n²)，当数组是逆序时。
• 最好情况时间复杂度：O(n)，当数组已经有序时（优化版本）。
• 平均时间复杂度：O(n²)。

冒泡排序是一种稳定的排序算法，适合小规模数据的排序。对于大规模数据，更高效的排序算法如快速排序或归并排序更为适用。