直观理解冒泡排序的两层循环

[jrainlau]

冒泡排序号称是最简单的排序算法，其原理要理解起来确实是非常简单，这里直接摘抄其他人总结的定义：

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
——摘抄自菜鸟笔记

然后经典的冒泡排序算法可以这样写：

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

原理我明白了，但是这段代码我却没看懂。它有两层循环，分别是什么意思呢？外层循环的 i < len 是什么，内层循环的 j < len - 1 - i 又是什么意思？盯着代码看了半天没理解过来，没想到直接动手在草稿纸上演算一遍就都明白了。接下来我就记录一下我在草稿纸上是怎么演算的。

---

首先假定我们有一个数组 [4, 3, 2, 1, 0]，排序的次数从0开始算起：

第0次排序

可以看到，我们一共进行了4次判断（看箭头），直接把最大的 4 给挪到最右边了。

第1次排序

由于最大的 4 已经挪到最右边了，因此我们不需要再把倒数第二个数和它进行比较，因此只进行了3次判断。

第2次排序

同理，由于最大的 4 在最右，次大的 3 在次右，因此只需要进行2次判断即可。

第3次排序

只剩下两个数字了，直接对它们进行比较即可。

---

通过上述的演算可以发现，我们一共进行了4次排序，也就是代码中的外层循环 len - 1 的次数。

而通过观察演算结果的橙黄色部分可以发现，在第 i 次排序的时候，我们就有 i 个数字是橙色的，也就是已经被挪到右边的。不难发现，在第 i 次排序的时候，我们可以跳过橙色的部分，只需要做 len - 1 - i 次判断就可以了：

• 第0次排序，可以跳过0个橙色数字，需要做 len - 1 - 0，也就是4次判断；
• 第1次排序，可以跳过1个橙色数字，需要做 len - 1 - 1，也就是3次判断；
• 第2次排序，可以跳过2个橙色数字，需要做 len - 1 - 2，也就是2次判断；
• 第3次排序，可以跳过3个橙色数字，需要做 len - 1 - 3，也就是1次判断。

因此，内层循环的 len - 1 - i 的意思就是“在第 i 轮的时候可以不判断最后的第 i 个数字”。

最后附上有注释的代码作为本文的结尾吧！

function bubbleSort(arr) {
  for (let i = 0, len = arr.length; i < len - 1; i++) { // 一共进行 arr.length - 1 轮循环
    for (let j = 0; j < len - 1 - i; j++) { // 在第 i 轮的时候可以不判断最后的第 i 个数字（因为已经被挪到右边了） 
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

（完）