排序算法

冒泡排序

每次交换两个元素的位置，一直交换到最大/最小的元素到了最前面/后面。下次循环舍弃掉这个元素的位置，继续交换一轮。
好处是可以设置一个标识，比如我的代码里的swap。如果一个循环之后没有交换位置，就意味着此时的允许已经正确了，不需要继续循环。

function bubble(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swap = false
    for (j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap = true
        let tmp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
      }
    }
    if (!swap) {
      console.log('!swap')
      break
    }
  }
  return arr
}

平均时间复杂度O(n²)，最好情况O(n)，最坏情况O(n²)，空间复杂度O(1)。

Read more »