JavaScript 冒泡排序

Question

接下来要介绍的基本排序算法其核心思想是指对一组数据按照一定的顺序重新排列。重新排列时用到的技术是一组嵌套的 for 循环。其中外循环会遍历数组的每一项，内循环则用于比较元素。这些算法非常逼真地模拟了人类在现实生活中对数据的排序，例如纸牌玩家在处理手中的牌时对纸牌进行排序，或者教师按照字母顺序或者分数对试卷进行排序。

冒泡排序

我们先来了解一下冒泡排序算法，它是最慢的排序算法之一，但也是一种最容易实现的排序算法。

之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

这里有一个简单的冒泡排序的例子。我们从下面的列表开始：

E A D B H

经过第一次排序后，这个列表变成：

A E D B H

前两个元素进行了互换。接下来再次排序又会变成：

A D E B H

第二个和第三个元素进行了互换。继续进行排序：

A D B E H

第三个和第四个元素进行了互换。最后，第二个和第三个元素还会再次互换，得到最终顺序：

A B D E H

下面展示了冒泡排序的代码

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

function swap (A, i, j) {
  const t = A[i]
  A[i] = A[j]
  A[j] = t
}

第1轮要进行4次比较，得到 4,3,2,1,5
第2轮要进行3次比较，得到 3,2,1,4,5
第3轮要进行3次比较，得到 2,1,3,4,5
第4轮要进行2次比较，得到 1,2,3,4,5