losetime

1. 快速排序

function quickSort(arr, l, r){
  if(l>=r) return arr
  let left = l // 左指针!
  let right = r //右指针
  let pivot = arr[left] // 基准值
  // 开启排序
  while(left < right){  // 如果左指针小于右指针，才能继续，否则说明两个指针相遇了
    while(arr[left]<pivot && left<right){
      left++
    }
    while(arr[right]>pivot && left<right){
      right--
    }
    if(left<right){
      [arr[left],arr[right]] = [arr[right],arr[left]]
    } else {
      arr[left]=pivot
    }
  }
  quickSort(arr, l, left-1)
  quickSort(arr, left+1, r)
  return arr
}
let sortArr = [2,1,4,3,9,12,100,201,29,80,72,92,54,32,23]
console.log(quickSort(sortArr, 0, sortArr.length-1))

2. 归并排序

function mergeSort(arr){
    if(arr.length <= 1){
        return arr
    }
    let middle = Math.floor(arr.length / 2)
    let left = arr.slice(0, middle)
    let right = arr.slice(middle)
    return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right){
    let result = []
    while(left.length > 0 && right.length > 0){
        if(left[0]<right[0]){
        result.push(left.shift())
        }else {
        result.push(right.shift())
        }
    }
    return result.concat(left).concat(right)
}

3. 计数排序

• 主要思想

1. 通过定义一个目标数组内最大值和最小值区间长度的新数组
2. 把目标数组的值分别放入该数组对应的下标
3. 每次该数组下标对应的值要加1
4. 最后就会形成下面这样一个数组
   
5. 这个数组已经是排好序的，我们通过循环取出下标，下标所对应的值则是该下标出现的次数

• 注意

1. 计数排序是唯一一种时间复杂度可以达到O(n)的排序算法

function countSort(arr){
    let maxNum = Math.max(...arr)
    let minNum = Math.min(...arr)
    let counter = new Array(maxNum - minNum + 1).fill(0)
    let result = []
    for(let i=0;i<arr.length;i++){
        counter[arr[i]] = counter[arr[i]]+1
    }
    for(let i=0;i<counter.length;i++){
        result = result.concat(new Array(counter[i]).fill(i))
    }
    return result
}