冒泡排序

依次比较相邻值，如果右侧较小交换位置，每次比较最右侧得到剩余的最大值0-i，相当于把最大值冒泡出去。

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

function swap (arr, i, j) {
  arr[i] = arr[i] ^ arr[j]
  arr[j] = arr[i] ^ arr[j]
  arr[i] = arr[i] ^ arr[j]
}

选择排序

每次选出最小的，交换第一位和最小位，i-n-1

function selectSort (arr) {
    const n = arr.length
    for (let i = 0; i < n; i++) {
       let minIndex = i
       for (let j = i; j < n; j++) {
         minIndex = arr[j] < arr[minIndex] ? j : minIndex
       }
       swap(arr, i, minIndex)
    }
}

// 这里的交换函数不能用异或，因为i可能与j相等，会出现清零的错误
function swap (arr, i, j) {
   let temp = arr[i]
   arr[i] = arr[j]
   arr[j] = temp
}

插入排序

类似摸牌，依次搞定0-1，0-2...0-n-1的顺序

function insertSort (arr) {
   const n = arr.length
   for (let i = 1; i < n; i++) {
     for (let j = 0; j < i; j++) {
       if (arr[i] < arr[j]) {
          swap(arr, i, j)
       }
     }
   }
}

归并排序

递归，每次左侧排序，右侧排序，然后两个指针归并，相较上述3种，没有浪费比较行为

function mergeSort (arr) {
  if (arr.length <= 1) {
    return
  }
  process(arr, 0, arr.length - 1)
  console.log(arr)
}

function process (arr, l, r) {
  if (l === r) {
    return
  }
  let mid = l + ((r - l) >> 1)
  process(arr, l, mid);
  process(arr, mid+1, r); 
  merge(arr, l, mid, r)
}

function merge (arr, l, mid, r) {
  let newArr = []
  let p1 = l
  let p2 = mid + 1
  let i = 0
  while(p1 <= mid && p2 <= r) {
    newArr[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++]
  }
  while(p1 <= mid) {
    newArr[i++] = arr[p1++]
  }
  while(p2 <= r) {
    newArr[i++] = arr[p2++]
  }
  for (let k = 0; k < newArr.length; k++) {
    // 这一步是必须的，只有改变原数组，才能在递归传递出去，使每次有效
    arr[l++] = newArr[k]
  }
}

举例：求小和问题

快速排序

先等概率随机选个数，小于这个数放左边和大于这个数放右边，然后递归，每次这个数的顺序会被排好 注意：快排选取的数必须是随机数，不能选指定某个位置的数，因为可能会出现最差情况的例子，时间复杂度就到了O(n²)了，只有选随机数，才会是O(nlogn)

function quickSort (arr) {
  if (arr.length <= 1) {
    return
  }
  process(arr, 0, arr.length - 1)
  console.log(arr)
}

function process (arr, l, r) {
  if (l < r) {
      // 选数
      let random = l + Math.floor(Math.random() * (r - l + 1))
      console.log('random', random)
      // 将选出来的随机数放在最右边
      swap(arr, random, r)
      let p = partition(arr, l, r)
      process(arr, l, p[0]-1)
      process(arr, p[1]+1, r)
  }

}

function partition (arr, l, r) {
  let p1 = l - 1 // 小于区右边界
  let p2 = r // 大于区左边界
  while (l < p2) {
    if (arr[l] > arr[r]) { // 当前值和划分值比较
      swap(arr, l, --p2)
    } else if (arr[l] < arr[r]) {
      swap(arr, ++p1, l++)
    } else {
      l++
    }
  }
  swap(arr, r, p2) // 交换最右的划分值和右边界-1
  return [p1+1, p2] // 返回等于划分值区域的左边界和右边界
}

function swap (arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

举例：荷兰国旗问题

堆排序

堆排序用得较少，后续更新哈

总结

排序稳定性：相同大小元素的相对次序，排序前后不变