JavaScript 数据结构与算法之美 - 十大经典排序算法之冒泡排序

思想

• 冒泡排序只会操作相邻的两个数据。
• 每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
• 一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

特点

• 优点：排序算法的基础，简单实用易于理解。
• 缺点：比较次数多，效率较低。

动画
实现

function bubbleSort(arr) {
  console.time('正常版')
  const len = arr.length;
  if (len <= 1) return arr;
  // i < len - 1 是因为外层只需要 len-1 次就排好了，第 len 次比较是多余的。
  for (let i = 0; i < len - 1; i++) {
    // j < len - i - 1 是因为内层的 len - i - 1 到 len-1 的位置已经排好了，不需要再比较一次。
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  console.log('arr：' + arr)
  console.timeEnd('正常版')
}

优化原则： 当数据已经达到想要的效果以后程序还在接着走

优化1： 当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

代码实现

function bubbleSort1(arr) {
  console.time('优化版1')
  const len = arr.length;
  if (len <= 1) return arr;
  for (let i = 0; i < len - 1; i++) {
    let hasChange = false; // 提前退出冒泡循环的标志位
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        hasChange = true; // 表示有数据交换
      }
    }
    if (!hasChange) break; // 如果 false 说明所有元素已经到位，没有数据交换，提前退出
  }
  console.log('arr：' + arr)
  console.timeEnd('优化版1')
}

优化2： 设置⼀标志性变量pos,⽤于记录每趟排序中最后⼀次进⾏交换的位置。由于pos位置之后的记录均已交换到位,故在进⾏下⼀趟排序时只要扫描到pos位置即可。

实现

function bubbleSort2(arr) {
  console.time('优化版2');
  let i = arr.length - 1; //初始时,最后位置保持不变 
  while (i > 0) {
    let pos = 0; //每趟开始时,⽆记录交换 
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        pos = j; //记录交换的位置 
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
    if (pos == 0) break; //如果经过循环后pos没有变化标识没有数据交换故提前退出
    i = pos; //为下⼀趟排序作准备 
  }
  console.log('arr：' + arr)
  console.timeEnd('优化版2');
}

优化3： 传统冒泡排序中每⼀趟排序操作只能找到⼀个最⼤值或最⼩值,我们考虑利⽤在每趟排序中进⾏正向和反向两遍 冒泡的⽅法⼀次可以得到两个最终值(最⼤者和最⼩者) , 从⽽使排序趟数⼏乎减少了⼀半。

实现

function bubbleSort3(arr) {
  console.time('优化版3');
  let low = 0;
  let high = arr.length - 1; //设置变量的初始值 
  let tmp, j;
  while (low < high) {
    let hasChange = false  // 提前退出冒泡循环的标志位
    for (j = low; j < high; ++j) { //正向冒泡,找到最⼤者 
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
        hasChange = true  // 表示有数据交换
      }
    }
    if (!hasChange) break;  // 如果 false 说明所有元素已经到位，没有数据交换，提前退出
    hasChange = false  //最小值循环以后初始化提前退出标志
    --high; //修改high值, 前移⼀位
    for (j = high; j > low; --j) { //反向冒泡,找到最⼩者
      if (arr[j] < arr[j - 1]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
        hasChange = true   // 表示有数据交换
      }
    }
    if (!hasChange) break;   // 如果 false 说明所有元素已经到位，没有数据交换，提前退出
  }
  ++low;//修改low值,后移⼀位
  console.log('arr：' + arr)
  console.timeEnd('优化版3');
}

测试

const arr = [1, 2, 4,3, 5, 6, 7, 8];
const arr1 = [10, 1, 35, 61, 89, 36, 55];
bubbleSort(arr1)
bubbleSort1(arr1)
bubbleSort2(arr1)
bubbleSort3(arr1)

输出结果

arr：1,10,35,36,55,61,89
正常版: 11.446ms
arr：1,10,35,36,55,61,89
优化版1: 0.508ms
arr：1,10,35,36,55,61,89
优化版2: 0.329ms
arr：1,10,35,36,55,61,89
优化版3: 0.121ms

分析：

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

最后

此文若有出入，请指出！
此致，敬礼！