SOURCE

// 快排  核心思想是多次进行比较和交换；
// 其单词排序得思想是：先从数组中选择一个key值；
// 然后，q指针从右边开始扫描，遇到小于key值的元素停下;
// p指针从左边开始扫描，遇到大于key值的元素停下；
// 然后交换q和p指向的元素。
// 继续重复上面步骤，直至p指针和q指针相遇，则交换key值和两指针指向得位置得元素；
// 这样排序一次后，可确定key值的最终位置；
// 递归调用这个函数，分别对左区间和右区间进行排序；


// 单躺排序函数
function test(arr, left, right) {
    let key = left; //取基准元素
    while (left < right) {
        while (left < right && arr[right] >= arr[key]) right--; //从右边开始定位小于key的元素
        while (left < right && arr[left] <= arr[key]) left++; //从左边开始定位大于key的元素
        swap(arr,left,right);
        //打印交换过程
        console.log(arr)
    }
    //当左右指针重合时，交换key值和重合指针标记位置的元素
    swap(arr,key,left)
    return left;
}

//交换函数
function swap(arr,i,j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}


// test(arr,0,arr.length-1)
// console.log(arr)

function quickSort(arr,left,right){
    if(left>=right)return
    let key = test(arr, left, right);
    quickSort(arr,left,key-1);
    quickSort(arr,key+1,right);
}

const arr = [4, 1, 6, 5, 7, 2, 3]
quickSort(arr,0,arr.length-1);
console.log(arr)