冒泡排序

一个静态的湖面上有很多大小不一的气泡往上飘，大的先飘上来，中的在飘，小的最后飘上来，哈哈。

冒泡排序（bubble sort）也称作下沉排序（sinking sort）, 它重复比较相邻的两个元素，直到整个数组都没有数字可以在进行交换为止。

设计一个大元素慢慢冒上去的算法。[6, 3, 5, 8, 1, 4]

• 先比较 6 和 3， 6 比 3 大，交换

• 6 和 5 比较 ，6 比 5 大，交换

• 6 和 8 比较， 8 比 6 大，交换

• 8 和 1 比较， 8 比较 1 大，交换

• 8 和 4 比较，8 比 4 大，交换

这个时候 8 这个最大的值就到了最右边，最大的气泡冒上来了，下一次循环就不需要包括 8 这个元素了。

8 这个元素已经冒到最右边的位置了，标记为绿色

重复上面的交换过程

• 抽象

function bubble_sort (A) {
  A: 需要排序的数组

  返回：无
}

图1-1

图1-1 标绿色表示已排序的数字，最大的数字冒到右边，i 在第一次循环结束的时候指向第一大的值 i = 6 最大值为 8，第二循环结束指向第二大的值 i = 5 最大值为 6。经过很多次循环后 i 指向倒数第二大的值 2。整个循环结束。

图1-2

图1-2 内层循环负责把一个最大的数字慢慢冒上去。

function bubble_sort (A) {
  // 外层循环 - 递减  来确定整个循环的次数，即遍历多少轮
  // 最重要的作用是使下一轮不会重复对比最后一个元素，最后一个元素都是最大的数
  for (let i = A.length - 1; i >= 1; i--) {
    // 内层循环-递加
    // 两两比较，选中较大的数字进行交换，最后的i个数字已经排序完了，不需要在进行比较了
    for (let j = 1; j <= i; j++) {
      // 冒泡比较，j - 1对应的值如果大于 j 对应的值，交换
      // 确保 j 对应的值在 0 - j 区间始终是最大的
      A[j - 1] > A[j] && swap(A, j - 1, j)
      // 内层循环结束 j 指向 A[0] - A[j] 这个区间中最大的值
    }
    // 外层循环结束 A[i] - A[n - 1] 区间已排序
  }
}

// 交换两个值
function swap (A, i, j) {
  const t = A[i]
  A[i] = A[j]
  A[j] = t
}

const A = [5, 8, 1, 3, 2, 4, 6]
bubble_sort(A)
console.log(A) // [1, 2, 3, 4, 5, 6, 8]