js快速排序

快速排序

/** * 获取midValue的两种方式 * 使用splice，会修改原数组 * 使用slice，不会修改原数组 * O(n*logn) * 单独比较splice和slice，slice快很多 */

function quickSort(arr){
    
  const length = arr.length
  if(length === 0) return arr

  const midIndex = Math.floor(length/2)
  // splice修改原数组，返回被删除元素的数组
  const midValue = arr.splice(midIndex,1)[0]

  const left = []
  const right = []

  // 注意：这里不能直接用length，而是用arr.length，因为arr已经被splice修改
  for(let i=0;i<arr.length;i++){
    
    if(arr[i]<midValue){
    
      // 小于放在左
      left.push(arr[i])
    }else{
    
      //大于放在右
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([midValue],quickSort(right))
}

const arr = [1,6,2,7,8,5,3]
console.log(quickSort(arr));