Skip to main content

冒泡排序

冒泡排序是一种简单的排序算法，它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们的位置。

算法原理​

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。

代码实现​

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

时间复杂度​

  • 最坏时间复杂度：O(n²) - 当输入数组是逆序时
  • 最好时间复杂度：O(n) - 当输入数组已经排序时
  • 平均时间复杂度：O(n²)

空间复杂度​

  • 空间复杂度：O(1) - 只需要常数级的额外空间

优缺点​

优点​

  • 实现简单，容易理解
  • 对于小规模数据或基本有序的数据，效率较高

缺点​

  • 对于大规模数据，效率较低
  • 时间复杂度为 O(n²)，性能较差

适用场景​

  • 小规模数据排序
  • 基本有序的数据排序
  • 作为学习排序算法的入门示例