思想

从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到 length - 1 的位置。

image

实现

两种方法原理一样, 只是在选择i值上的策略不同

/*
  冒泡排序:
  平均时间复杂度:O(n2), 最差时间复杂度:O(n2), 是稳定排序, 需要额外空间O(1) 
 */
function buble1(array) {
  let temp = 0
  let flag = false
  for (let i = 0; i < array.length -1; i++) {
    for (let j = 0; j < array.length -1 -i; j++) {
      if (array[j] > array[j+1]) {
        flag = true
        temp = array[j+1]
        array[j+1] = array[j]
        array[j] = temp
      }
    }
    console.log(`方法1的第${i}次排序的结果: ${array}`);
    if(!flag) {//优化代码,方法2也可使用
      break
    }else {
      flag = false
    }
  }
}
function buble2(array) {
  let temp = 0
  for (let i = array.length -1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (array[j] > array[j+1]) {
        temp = array[j+1]
        array[j+1] = array[j]
        array[j] = temp
      }
    }
    console.log(`方法2的第${i}次排序的结果: ${array}`);
    
  }
}
let array = [3,9,-1,10,20]
buble1(array)
array = [3,9,-1,10,20]
buble2(array)