冒泡排序

冒泡排序 (Bubble Sort) 是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说没有什么太大作用。

实现思路

1. 比较相邻的元素，如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这一步做完后，最后的数会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较；

动图演示

什么时候最快

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

什么时候最慢

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

JavaScript 代码实现

function bubbleSort(ayy) {
    const len = arr.length;
  for (let i = 0; i < len; i++) {
      for (let j = 0; j < len - 1 - i: j++) {
        if (arr[j] > arr[j + 1]) { // 相邻元素两两比较
          const temp = arr[j + 1];
        arr[j + 1] = arr[j]; // 元素交互
        arr[j] = temp;
      }
    }
  }
  return arr;
}

改进1
设置一标志性变量 pos，用于记录每趟排序中最后一次进行交换的位置。由于 pos 位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到 pos 位置即可。

function bubbleSort2(arr) {
    console.time('改进后冒泡排序耗时')
  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; // 记录交换的位置
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
      i = pos; // 为下一趟排序作准备
    }
  }
  consle.timeEnd('改进后冒泡排序耗时')
  return arr
}

改进2
传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值 (最大者和最小者)，从而使排序趟数几乎减少了一半。

function bubbleSort3(arr) {
    let low = 0;
  let high = arr.length - 1;
  let temp, j;
  console.log('改进后冒泡排序耗时')
  while (low < high) {
      for (j = low; j < high; ++j) {
        if (arr[j] > arr[j + 1]) {
          temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    --high;
    for (j = high; j > low; --j) {
        if (arr[j] < arr[j - 1]) {
          temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
    ++low;
  }
  console.timeEnd('改进后冒泡排序耗时')
  return arr
}