排序【4】— 快速排序

快速排序的思路：

思路1：选择一个基准值(随意)，然后比基准值小的，推入左边，比基准值大的推入右侧

    Array.prototype.quickSort = function () {
        // 定义递归出口
        if (this.length <= 1) {
            return this;
        }
        let target = this[0]
        let left = []
        let right = []
        for (let i = 1; i < this.length; i++) {
            // 如果比基准数大就推入左数组
            if (this[i] < target) {
                left.push(this[i])
            // 否则就推入右数组
            } else {
                right.push(this[i])
            }
        }
        // 采用递归方式, 继续对左右数组进行排序操作
        return [...left.quickSort(), target, ...right.quickSort()]
    }

思路2：
选择一个基准值，从右边开始找比基准值小的，再从左边找比基准值大的，交换这两个元素。这样循环下来，直到左边和右边相遇，相遇了之后将基准值和相遇点交换。则此时基准值左侧都小于基准值，基准值右侧都大于基准值。然后再递归排序基准值左边和右边的元素。

Array.prototype.quickSort = function (start=0, end=this.length-1) {
    //定义递归出口
    if(end - start < 1) {
        return;
    }
    // 选定基准值
    const target = start;
    // 开始从左右两边往中间查找
    let left = start;
    let right = end;
    // 左右相遇则证明整理完毕
    while(left<right) {
        // 在右边找比基准值小的
        while(left<right && this[right] >= this[target]) {
            right--;
        }
        // 在左边找比基准值大的元素
        while(left<right && this[left] <= this[target]) {
            left++;
        }
        
        // 交换位置
        [this[left], this[right]] = [this[right], this[left]];
    }
    // 收敛到中间后，和基准值交换位置，此时基准值左边都比基准值小，右边都比基准值大
    [this[left], this[target]] = [this[target], this[left]];
    // 继续对左右两边进行排序
    this.quickSort(start, left-1)
    this.quickSort(left+1, end);
}