冒泡排序

插入排序

选择排序

归并排序

分治思想，分治算法一般都是用递归来实现的。
写递归的技巧：分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。
归并排序不是原地排序算法。
在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)

function foo(arr) {
  const merge_sort = (left, right) => {
    // 递归结束条件：
    if(left >= right) return
    // 这样可以避免加法越界
    let pivot = left + Math.floor((right-left)/2)
    merge_sort(left, pivot)
    merge_sort(pivot+1, right)
    //这里要注意！输入的是节点
    merge(left, right, pivot)
  }
  const merge = (left, right, pivot) => {
    let temp = [], i = left, j = pivot + 1, k = 0
    // 注意中间是&&
    while(i<=pivot && j<=right) {
      if(arr[i] <= arr[j]){
        temp[k] = arr[i]
        i++
        k++
      } else {
        temp[k] = arr[j]
        j++
        k++
      }
    }
    // 找到是哪一个数组没被遍历完，直接接到temp后面
    // 注意等号
    let start = i <= pivot ? i : j
    let end = i <= pivot ? pivot : right
    while(start<=end) {
      temp[k++] = arr[start++]
    }
    // 注意这里arr要从left开始
    for(let i=0; i<=right-left; i++){
      arr[left+i] = temp[i]
    }
  }
  merge_sort(0, arr.length-1)
  return arr
}

快速排序

快排核心思想：

function foo1(arr) {
  const quick_sort = (left, right) => {
    if(left>=right) return
    let pivot = build(left, right)
    quick_sort(left, pivot-1)
    quick_sort(pivot+1, right)
  }
  const build = (left, right) => {
    let pivot = arr[right]
    let i = left
    // 这里pivot等于数组最后一个值，遍历数组时要去掉这个pivot
    for(let j=left; j<=right-1; j++){
      if(arr[j] < pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
        i++
      }
    }
    // arr[right]最后要和arr[i]交换，因为左边[0,i-1]区间都是小于pivot的值
    [arr[right], arr[i]] = [arr[i], arr[right]]
    return i
  }
  quick_sort(0, arr.length-1)
  return arr
}