JavaScript快速排序

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

实现步骤：

• 选择一个基准元素target（一般选择第一个数）
• 准备两个数组容器，遍历数组，逐个与基数比对，较小的放左边容器，较大的放右边容器；
• 递归处理两个容器的元素，并将处理后的数据与基数按大小合并成一个数组，返回。

时间复杂度：O(nlogN)

手写实现：

let quickSort=(arry)=>{
    if(arry.length <= 1) return arry;
    let left=[];
    let right=[];
    let middle=arry[0];//选择基准为数组第一个元素
    for(let i=1;i<arry.length;i++){//两个容器，左小，右大
        if(arry[i] < middle) left.push(arry[i]);//从第二个元素开始遍历
        else right.push(arry[i]);
    }
    //递归2个容器并合成
    return [...quickSort(left),middle,...quickSort(right)];
    // return quickSort(left).concat(middle,quickSort(right))
}

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