1. 冒泡排序

算法描述

1. 比较相邻的元素，如果前面的数大于后面的元素，则交换两个数的位置。第一次遍历后，最大的数会被放到数组的最后位置，即 array[length - 1]。
2. 第二次遍历时跳过最后一个元素，因为该元素通过第一次遍历已经确定是最大值。
3. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示

算法实现

这里需要注意的是两层循环的边界。
第一层循环因为是两两比较，所以最后一个元素已经和前一个元素比较过了，所以就没必要遍历了，所以第一层循环 i < arr.length - 1。
第二层循环中，后面的 i 个元素已经为排序好的元素了，所以也没必要再遍历了，所以第二层循环 j < arr.length - 1 - i。

/**
 * 交换数组中的两个元素
 * @param {number[]} arr
 * @param {number} i
 * @param {number} j 
 */
const swap = (arr, i, j) => {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
/**
 * 冒泡排序
 * @param {number[]} arr 数值数组
 */
const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
      }
    }
  }
  return arr
}

这里的时间复杂度为 o(n^2)。