冒泡排序

冒泡排序是最简单的，也是效率最差的一种排序算法。我们学习冒泡排序一般都是为了练习编程语言中的双层循环，虽然没有什么实际的意义，但是有时候面试中可能还会考到，另外对于一些数据量比较小的数组排序，也可以使用它。

原理

冒泡排序的原理是，两两对比数组中的每个元素，如果后面的一个元素比前面的大，那么就交换它们的顺序，直到所有的元素都比对一遍。

因为在每次遍历后，都能找到最大的元素，并放到最右边，就像是冒泡，所以就有了冒泡排序这个名字。

例如，一个数组，它的元素是 [3, 1, 5, 9, 6, 2 ]。那么第一遍循环：

• 先比对 3 和 1，3 比 1 大，所以交换顺序，变成了 1 和 3 。
• 然后 3 和 5 再对比， 3 没有 5 大，不用交换位置。
• 在比对 5 和 9 ， 5 没有 9 大，也不用交换位置。
• 9 再和 6 对比，9 大于 6 所以这两个交换位置。
• 最后 9 再和 2 对比，9 比 2 大，把他们两个交换顺序。

这样第一遍最大的元素就找出来了，放到了最后一位，数组变成了 [1, 3, 5, 6, 2, 9]。

然后第 2 遍，

• 比对 1 和 3，这两个不用交换。
• 再比对 3 和 5，也不用交换。
• 5 和 6 也不用交换。
• 6 和 2 需要交换变成 2 和 6。
• 最后 6 和 9 就不用对比了，因为 9 我们知道他是已经排序好的最大的元素。

这样我们的结果就变成了，135269。 好，按照这个顺序对比下去，我们下一次会得到 132569，再下一次得到 123569，这样全部遍历完成之后，排序的结果就是 123569。 我们来看一下代码：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

这里我定义了 bubbleSort函数：

• 接收一个数组作为参数，对这个数组进行排序。
• 在里边使用了双层循环，第一层循环，是确保所有数组元素都比对一遍，那么这里，我们就循环数组长度这么多次。
• 第二层循环，在每次循环时：
  • 比对相邻的两个元素的大小，如果前面的元素大于后边的元素，就把这两个元素交换位置。
  • 这里利用到了数组的解构赋值语法，来让我们用 1 行代码，就能交换两个元素的位置。这个意思就是说我们先定义一个数组 [arr[j+1], arr[j]]，把后面元素的值作为第一个元素，前面元素的值作为第 2 个元素，而前面的解构赋值语法因为就和变量赋值一样，那么这里的意思就是说，把 arr[j] 的值改成 arr[j+1] 的值，把 arr[j+1] 的值改成 arr[j] 的值。因为后面的这个数组，是我们创建的新的数组，所以说它不会改变原数组的值，只有前边的这一部分会改变，这样就完成了数组的交换。
  • 这里 j < arr.length - i - 1 是因为每次外层循环遍历完成之后，对应数量的元素就已经排好序了，放到了数组右侧，就不用再比对它们了。

    如果你对这个语法不熟悉或者是想系统的学习 JavaScript 的语法，可以看我编写的《JavaScript 基础语法详解》一书，各大电商平台都有销售，并且经常会有满 100 减 50、或者半价活动。

好，最后排序完之后我们返回这个数组，我们用 315962 这个数组来测试一下，打印一下调用 bubbleSort 的函数之后，数组的排序结果，我们执行一下这个文件：

node bubble_sort.js

可以看到它打印出来了排序好后的数组，123569，

优化代码

上边的代码还可以继续优化一下：

function bubbleSort(arr) {
  let swapped;
  for (let i = 0; i < arr.length; i++) {
    swapped = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

现在，我们的算法，如果内层循环已经排好序了，但是因为外层循环仍然需要遍历完所有次数，那么最后几次循环其实什么都没操作，所以我们可以在内部循环排好序之后，就停止外层的循环。判断是否排好序的依据是，内层循环没有发生元素交换。那么这样，我们可以先定义一个指示变量，swapped，在外层循环中，把它设置为 false，在内层循环中，如果发生了交换就把它设置为 true，当内层没有发生交换时，那么 swapped 就保持为 false，这样就可以中断外层循环了。

这时，我们在旧的排序算法函数中，外层循环的最后，打印一下 i 的值，可以看到它执行了 6 次：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
    console.log(i);
  }
  return arr;
}

0;
1;
2;
3;
4;
(5)[(1, 2, 3, 5, 6, 9)];

在优化后的算法中，我们也打印一下 i 的值，可以看到它执行了 5 次：

function bubbleSort(arr) {
  let swapped;
  for (let i = 0; i < arr.length; i++) {
    swapped = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    console.log(i);
    if (!swapped) break;
  }
  return arr;
}

0;
1;
2;
3;
(4)[(1, 2, 3, 5, 6, 9)];

时间复杂度

冒泡排序在最坏情况下，时间复杂度是 O(n2)，也就是说，当原数组完全是反向排序的，从大到小排列的，那么算法需要对每个元素都过一遍并且交换一次，第 1 遍需要比对和交换 n 个元素，第 2 遍是 n-1 第三遍是 n-2，以此类推一直到 0，加起来就是 n(n-1)/2，大 O 取得是近似值，所以算法复杂度就是 O(n2)。

小结

好了这个就是冒泡排序的简介和实现方式，你学会了吗？如果有帮助请三连，想学更多的前端开发知识，请关注峰华前端工程师，感谢观看！