快速排序

[Betty985]

思想

• 在数据集中，选择一个元素作为基准；
• 小于基准的元素放到基准的左边，大于基准的元素放到基准的右边。这个操作叫分区。分区操作结束后，基准元素所处的元素就是它最后的位置；
• 对基准左右的子集，不断重复第一步和第二步，直到所有子集只剩一个元素。

  代码

  function quickSort(arr){
  if(arr.length<=1) return arr
  let paritionIndex=Math.floor(arr.length/2)
  let tmp=arr[paritionIndex]
  let left=[]
  let right=[]
  for(let i=0;i<arr.length;i++){
      if(i==paritionIndex) continue
      if(arr[i]<tmp){
          left.push(arr[i])
      }else{
          right.push(arr[i])
      }
  }
  return quickSort(left).concat([tmp],quickSort(right))
  }