冒泡排序以及改进方案

冒泡排序以及改进方案

介绍：

冒泡排序属于一种典型的交换排序（两两比较）。冒泡排序就像是把一杯子里的气泡一个个往上冒一样。它不断比较相邻的元素，如果顺序不对就像水泡一样交换它们的位置，直到整个序列像水泡一样，按照大小顺序排列好。当它发现一轮遍历中没有发生交换，就像是水泡都冒完了一样，就知道排序完成了。

图示：

冒泡排序性能

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
冒泡	O(n）	O(n2)	O(n2)	1	稳定

普通版本的冒泡排序

通过简单的两层遍历，就可以实现了：

const arr = [5, 3, 6, 2, 10];

const bubbleSort = (arr) => {
  if (arr.length <= 0) return;
  const length = arr.length;

  // 外层循环
  for (let i = 0; i < length; i++) {
    console.log("🚀 bubbleSort ~ i:", arr[i]);

    // 内层循环
    for (let j = 0; j < length - i - 1; j++) {
      console.log("🚀 bubbleSort ~ j:", arr[j]);
      // 需要交换
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }

    console.log("数组为", arr);
  }
  console.log("最终数组为", arr);
};

bubbleSort(arr);

第一次改进：

当一个数组大小不是很混乱的时候，我们没必要每次都去交换：

例如：2,1,3,4,6 这样的数组，我们在第一次交换的时候就已经排好序了（1,2,3,4,6）,我们无需再基于1,2,3,4,6排序，改进如下：

const arr = [5, 3, 6, 2, 10];

const bubbleSort = (arr) => {
  if (arr.length <= 0) return;
  const length = arr.length;

  // 外层循环
  for (let i = 0; i < length; i++) {
    console.log("🚀 bubbleSort ~ i:", arr[i]);
    // 如果上次内层循环没有交换过，那么下次内层循环没必要继续了
    let ifChanged = false;
    // 内层循环
    for (let j = 0; j < length - i - 1; j++) {
      console.log("🚀 bubbleSort ~ j:", arr[j]);
      // 需要交换
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        ifChanged = true; // 标记为交换过
      }
    }
    if (!ifChanged) {
      break;
    }

    console.log("数组为", arr);
  }
  console.log("最终数组为", arr);
};

bubbleSort(arr);

第二次改进：

最后一次交换位置将整个数组分为了两部分：之前是未排序部分，之后是已排序部分。如此一来，下一次冒泡排序就只需在未排序部分进行冒泡排序即可。 根据这个思路再进行代码改进：

const arr = [5, 3, 6, 2, 10];

const bubbleSort = (arr) => {
  if (arr.length <= 0) return;
  const length = arr.length;
  // 记录上次交换的索引
  let sortIndex = length - 1;
  // 外层循环
  for (let i = 0; i < length; i++) {
    console.log("--------");
    // 如果上次内层循环没有交换过，那么下次内层循环没必要继续了
    let ifChanged = false;
    // 内层循环
    for (let j = 0; j < sortIndex; j++) {
      console.log("🚀 bubbleSort ~ j:", arr[j]);
      // 需要交换
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        ifChanged = true; // 标记为交换过
        lastIndex = j; // 记录最后一次交换的位置
      }
    }
    sortIndex = lastIndex; // 让排序到最后一次交换位置结束
    if (!ifChanged) {
      break;
    }
    console.log("数组为", arr);
  }
  console.log("最终数组为", arr);
};

bubbleSort(arr);

 (!ifChanged) {
      break;
    }
    console.log("数组为", arr);
  }
  console.log("最终数组为", arr);
};

bubbleSort(arr);