JS实现冒泡排序及优化

实现原理

数组中有n个数，从第一个数开始，逐个比较相邻的两数，如果前面的大于后面的，交换位置，将比较大的数往后排。

实现

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {  // 比较轮数
    for (let j = 0; j < arr.length - 1 - i; j++) {  // 每轮比较次数，由于每次最后一个都是最大值，每轮少比较i次 
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr;
}

优化1: len

let len = arr.length  // 将len取出，避免每轮循环都去获取
for (let i = 0; i < len - 1; i++) {
  for (let j = 0; j < len - 1 - i; j++) {
    // ...
  }
}

优化2: 数值边缘检测

for (let i = 0; i < len - 1; i++) {
  for (let j = 0; j < len - 1 - i; j++) {
    if(arr[j] > Number.MAX_VALUE || arr[j] < -Number.MAX_VALUE) return "数值溢出！"
  }
}

优化3: 本轮没有交换的标志位

形如[1,2,3,4,6,5]这种数组，只需比较一轮就已经排好了。
所以我们加一个标志位，每次外层循环开始前将标志位置为true，内层循环过程中，出现两数交换时，置为false。
如果内层循环没有任何两数进行交换，标志位为true，表示排序完成。 这样我们就可以减少不必要的排序，提高性能

function bubbleSort(arr) {
  let done  // 已经完成的标志位
  let len = arr.length
  for (let i = 0; i < len - 1; i++) {
    done = true
    for (let j = 0; j < len - 1 - i; j++) {
      if(arr[j] > Number.MAX_VALUE || arr[j] < -Number.MAX_VALUE) return "数值溢出！"
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        done = false
      }
    }
    if(done){
      return arr
    }
  }
  return arr;
}