快速排序

[HerokunTan]

时间复杂度：O(nlogn)
空间复杂度：O(logn)
非稳定排序
原地排序

快速排序也属于分治算法的一种
快速排序的平均时间复杂度也是O(nlogn)，不过它不需要像归并排序那样，还需要一个临时的数组来辅助排序，这可以节省掉一些空间的消耗，而且他不像归并排序那样，把两部分有序子数组汇总到临时数组之后，还得在复制回源数组，这也可以节省掉很多时间。

要注意的是：快速排序的最坏时间复杂度是O(n2)

let testArr =  [8,5,2,6,9,3,1,4,0,7]

function quickSort(arr){
    function sort(left,right) {
        if(left<right) {
            let mid = partition(left,right)
            sort(left,mid-1)
            sort(mid,right)
        }
        return arr
    }
    function partition(left,right){
        let pivot =  arr[Math.floor((right + left) / 2)]
        let i = left
        let j = right
        let temp
        while (i<=j){
            while(arr[i]<pivot){i++}
            while(arr[j]>pivot){j--}
            if(i<=j) {
                temp = arr[i]
                arr[i++] = arr[j]
                arr[j--]  =temp
            }
        }
        return i
    }
    sort(0,arr.length-1)
    return arr
}