冒泡

function bubbleSort(arr) {
  for (let i=0; i<arr.length-1; i++) {
    for (let j=1; j<=arr.length-1-i; j++) {
      if (arr[j] < arr[j-1]) {
        [arr[j], arr[j-1]] = [arr[j-1], arr[j]]
      }
    }
  }

  return arr
}

bubbleSort([1, 3, 5, 2, 8, 5, 1])

1. 外层循环：每次遍历后，最大的元素会“冒泡”到数组末尾。需要处理len-1次就能把数组排好序。
2. 内层循环：内层循环用于两两比较，值大的放后面。内层循环的范围会随着外层循环的进行而减少。内循环遍历len-1-i

• 时间复杂度：O(n^2^)
• 空间复杂度：O(1)

优化：O(n) 当数组有序时，冒泡排序时间复杂序为O(n) 思路：如果在内层循环中没有发生任何交换，说明数组已经排序完成，可以提前结束排序过程。

function bubbleSort(arr) {
  for (let i=0; i<arr.length-1; i++) {
    let swapped = false
    for (let j=1; j<=arr.length-1-i; j++) {
      if (arr[j] < arr[j-1]) {
        swapped = true
        [arr[j], arr[j-1]] = [arr[j-1], arr[j]]
      }
    }
    if (!swapped) break
  }

  return arr
}

bubbleSort([1, 2, 3])

• 时间复杂度：O(n^2^)
  • 最坏情况：O(n^2^)
  • 最好情况：O(n)。当数组已经排序时，只需要进行一次遍历即可完成排序
• 空间复杂度：O(1)

选择

function selectSort(arr) {
  for (let i=0; i<arr.length; i++) {
    for (let j=1+i; j<arr.length; j++) {
      if (arr[j] < arr[i]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
  return arr
}

arr = [5,4,3,2,1,6]
selectSort(arr)

1. 外层循环：每次处理后，使i是i之后数据的最小值。
2. 内层循环：内层循环用于两两比较，值小的放前面。

• 时间复杂度：O(n^2^)
• 空间复杂度：O(1)

插入

插入排序的工作步骤：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5。

function insertSort(arr) {
  for (let i=1; i<arr.length; i++) {
    let j = i-1
    let tempVal = arr[i]
    while (j >=0 && tempVal < arr[j]) {
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = tempVal
  }
  return arr
}


let arr = [1, 3, 5, 2, 8, 5, 1]
insertSort(arr)

1. 头指针指向数组下标i。arr[i]插入下标0到i-1的有序数组中
2. 要用tempVal暂存要插入的值。因为在插入比对的过程中，数据后移，会覆盖

• 时间复杂度：O(n^2^)
  • 最坏情况：O(n^2^)
  • 最好情况：O(n)。当数组已经是有序时，每个元素只需要与前一个元素进行比较，不需要移动
  • 平均情况：O(n^2^)
• 空间复杂度：O(1)

快排

function quickSort(arr, head, tail) {
  if (head >= tail) return

  const quickSortDetail = (head, tail) => {
    while (head < tail) {
      while (arr[tail] >= arr[head] && head < tail) { // 1
        tail--
      }
      [arr[tail], arr[head]] = [arr[head], arr[tail]]
      while (arr[head] <= arr[tail] && head < tail) { // 2
        head++
      }
      [arr[tail], arr[head]] = [arr[head], arr[tail]]
    }

    return head
  }
  
  const key = quickSortDetail(head, tail)
  quickSort(arr, head, key-1)
  quickSort(arr, key+1, tail)
  return arr
}

let arr = [1, 3, 5, 2, 8, 5, 1]
// let arr = [6,22, 4,5,7,7888,32]
quickSort(arr, 0, arr.length-1)

1. 一次快排：左边不大于基准值；右边不小于基准值。返回一次快排后基准值下标
2. 头指针head，尾指针tail。初始设基准值为头指针的值：temp = arr[head]。 比较，不断交换头尾指针，直到相遇
3. 1，2 至少要有一处 >= , <=, 否则会死循环
4. 这种做法，头尾指针必有一个是基准值。对比头尾指针，也是和基准值对比，达到左边不大于基准值；右边不小于基准值

// 测试 [6, 22, 4, 5, 7, 7888, 32]
[6, 22, 4, 5, 7, 7888, 32] head 0 tail 6
[6, 22, 4, 5, 7, 7888, 32] head 0 tail 3
[5, 22, 4, 6, 7, 7888, 32] head 0 tail 3 swap
[5, 22, 4, 6, 7, 7888, 32] head 1 tail 3
[5, 6, 4, 22, 7, 7888, 32] head 1 tail 3 swap
[5, 6, 4, 22, 7, 7888, 32] head 1 tail 2
[5, 4, 6, 22, 7, 7888, 32] head 1 tail 2 swap
[5, 4, 6, 22, 7, 7888, 32] head 2 tail 2
// 返回key为2

// 测试 [6, 22, 4, 7, 7888, 4, 32]
[6, 22, 4, 7, 7888, 4, 32] head 0 tail 6
[6, 22, 4, 7, 7888, 4, 32] head 0 tail 5 tail--
[4, 22, 4, 7, 7888, 6, 32] head 0 tail 5 swap
[6, 22, 4, 7, 7888, 4, 32] head 1 tail 5 head++
[6, 4, 4, 7, 7888, 22, 32] head 1 tail 5 swap
[6, 4, 4, 7, 7888, 22, 32] head 1 tail 2 tail--

// 这就是为什么 快排代码1，2 至少要有一处 >= , <=, 否则两个4会一直在交换，死循环，

• 时间复杂度：O(nlog(n))。O(log(n))次快排，每次O(n) ==> O(log(n)) * O(n) ==> O(nlog(n))

归并

function arrayMerge(left, right) {
  let result = []
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  if (left.length) {
    result = result.concat(left)
  } else {
    result = result.concat(right)
  }
  return result
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr
  const middleIndex = Math.floor(arr.length/2)

  const left = mergeSort(arr.slice(0, middleIndex))
  const right = mergeSort(arr.slice(middleIndex))

  return arrayMerge(left, right)
}



let arr = [1, 3, 5, 2, 8, 5, 1]
console.log(mergeSort(arr))

1. 先一分二，直至只有一个元素；再组合，数组合并

mergeSort([1, 3, 5, 2, 8, 5, 1])
  -> mergeSort([1, 3, 5])
      -> mergeSort([1]) -> [1]
      -> mergeSort([3, 5])
          -> mergeSort([3]) -> [3]
          -> mergeSort([5]) -> [5]
          -> arrayMerge([3], [5]) -> [3, 5]
      -> arrayMerge([1], [3, 5]) -> [1, 3, 5]
  -> mergeSort([2, 8, 5, 1])
      -> mergeSort([2, 8])
          -> mergeSort([2]) -> [2]
          -> mergeSort([8]) -> [8]
          -> arrayMerge([2], [8]) -> [2, 8]
      -> mergeSort([5, 1])
          -> mergeSort([5]) -> [5]
          -> mergeSort([1]) -> [1]
          -> arrayMerge([5], [1]) -> [1, 5]
      -> arrayMerge([2, 8], [1, 5]) -> [1, 2, 5, 8]
  -> arrayMerge([1, 3, 5], [1, 2, 5, 8]) -> [1, 1, 2, 3, 5, 5, 8]

二叉树遍历

      A
     / \
    B   C
   / \   \
  D   E   F

const root = {
  val: "A",
  left: {
    val: "B",
    left: {
      val: "D"
    },
    right: {
      val: "E"
    }
  },
  right: {
    val: "C",
    right: {
      val: "F"
    }
  }
}

function preOrder(root) {
  if (!root) return
  console.log(root.val)
  preOrder(root.left)
  preOrder(root.right)
}

function middleOrder(root) {
  if (!root) return
  middleOrder(root.left)
  console.log(root.val)
  middleOrder(root.right)
}

function postOrder(root) {
  if (!root) return
  postOrder(root.left)
  postOrder(root.right)
  console.log(root.val)
}

// 测试
preOrder(root) // A B D  E C F
middleOrder(root) // D B E A C F
postOrder(root) // D E B F C A

x序遍历，指根结点【前、中、后】

• 前：根左右
• 中：左根右
• 后：左右根

参考： 十大排序算法超全大综合，动图演示，你真的值得拥有！ (opens new window)