冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

算法步骤

比较相邻元素，如果当前值比后一个元素值大，则交换两个元素。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

动图演示

代码实现

// 从小到大排序
// 每一轮排序结束，大值就排到末尾，大值逐渐往后冒泡
// 循环次数为(n-1)+(n-2)+(n-3)+...+(n-(n-1))
// 从1~n-1，一共有n-1个元素，即上面表达式中有n-1个n，上面示例简化为(n-1)n
// 所以复杂度为O(n^2)
function bubbleSort(arr) {
  // 排序轮数为 length - 1 次
  // 每一轮结束，最大值就冒泡到末尾了
  for (let i = 0; i < arr.length - 1; i++) {
    // 后面的i个元素已经是按顺序排列好的了，不需要在排
    // arr.length - i - 1 保证j + 1存在
    for (let j = 0; j < arr.length - i - 1; j++) {
      // 前一个比后一个大，交换位置
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

const arr = [6, 3, 5, 2, 4, 1]

bubbleSort(arr)
console.log(arr)