SOURCE

/**
 * 实现原理
 * 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。
 */

function quickSort(arr,left,right){
    let len = arr.length,
        partitionIndex
        left = typeof left !== 'number' ? 0 :left
        right = typeof right !== 'number' ? 0 :right
       
    if(left < right){
        partitionIndex = partition(arr,left,right)
        quickSort(arr,left,partitionIndex -1)
        quickSort(arr,partitionIndex+1,right)
    }
    return arr
}

function partition(arr,left,right){
    let pivot = left,
        index = pivot + 1
    for(let i=index;i<=right;i++){
        if(arr[i] < arr[pivot]){
            swap(arr,i,index)
            index++
        }
    }
    swap(arr,pivot,index-1)
    return index-1
}

function swap(arr,i,j){
   let temp = arr[i]
   arr[i] = arr[j]
   arr[j] = temp
}

console.log(quickSort([6,7,4,2,5],0,5))