算法-排序-快速排序

原理

    快速排序（Quicksort）是对冒泡排序的一种改进。

    通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

javaScript

function quickSort(arr){

  if(arr.length <= 1){

    return arr

  }

  let midIndex = Math.floor(arr.length/2)

  let mid = arr.splice(midIndex, 1)[0]

  let left = [], right = []

  for(let i=0; i<arr.length;i++){

    if(arr[i]<mid){

        left.push(arr[i])

    }else {

        right.push(arr[i])

    }

  }

 return quickSort(left).concat([mid], quickSort(right))

}

let arr3 = [3, 8, 1, 2, 9, 3, 7, 5, 8]

quickSort(arr3)