动画

实现

• 思路
  • 比较所以相邻元素，如果第一个比第二个大，则交换他们
  • 一轮下来，可以保证最后一个数是最大的
  • 执行n-1轮，就可以完成排序
• 时间复杂度O(n^2)

  两层 for 循环

const array = [5, 6, 3, 2, 8];
const bubble = (arr) => {
  for (let i = 0, len = arr.length; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (arr[j + 1] < arr[j]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
}
console.log(array); // [ 2, 3, 5, 6, 8 ]

上面的写法，时间复杂度始终都是 ，我们试着把它优化一下。
优化思路：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

const array = [5, 6, 3, 2, 8];
const bubble = (arr) => {
  for (let i = 0, len = arr.length; i < len; i++) {
    let hasChange = false; // 标志这一轮是否有数据交换，用于提前退出
    for (let j = 0; j < len; j++) {
      if (arr[j + 1] < arr[j]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
        hasChange = true;
      }
    }
    if(!hasChange) break; // 说明这一轮没有数据交换，可以退出
  }
}
console.log(array); // [ 2, 3, 5, 6, 8 ]

分析

• 第一，冒泡排序是原地排序算法吗 ？
  冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
• 第二，冒泡排序是稳定的排序算法吗 ？
  在冒泡排序中，只有交换才可以改变两个元素的前后顺序。
  为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序。
  所以冒泡排序是稳定的排序算法。
• 第三，冒泡排序的时间复杂度是多少 ？
  最佳情况：T(n) = O(n)，当数据已经是正序时。
  最差情况：T(n) = O(n^2)，当数据是反序时。
  平均情况：T(n) = O(n^2)。