// 快速排列 // 思路：选择数组中的一个值作为基准，将数组中小于该值的数置于该数之前，大于该值的数置于该数之后，接着对该数前后的两个数组进行重复操作直至排序完成。 // 参考：https://www.cnblogs.com/et-008/p/16472607.html // 时间复杂度 最好O(nlg(n)) 最坏：O(n2) | 空间：O(nlgn)

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

const arr = [9, 4, 3, 1, 6, 3, 8, 7];
console.log(quickSort(arr)) 




function quickSort1(arr) {
    const len = arr.length;
    if (len < 2) return arr;
    let left = [],right=[];
    for(let i=1;i<len;i++){
        if(arr[i] < arr[0]) {
            left.push(arr[i])
        }else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([arr[0]],quickSort(right))
}
console.log(quickSort1(arr))