js 实现快速排序

// 快速排序
// 稳定性
// 快速排序是以两个游标（指针）双向遍历，当两个指针相遇则遍历结束，并将相遇位置与基准值进行交换，递归出口为左游标>=右游标
// 快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了
function quickSort(arr) {
    let tmpArr = [...arr]; //复制数组
    return quick(tmpArr, 0, tmpArr.length - 1);
}
function quick(arr, i, j) {
    if (j - i <= 0) return; //说明数组只有一个值了
    let left = i,
        right = j;
    let base = left; //以左边第一个为基准值
    let center = arr[base];
    while (left < right) {
        //开始循环了
        //每次循环包括从右往左和从左往右
        while (left < right && center < arr[right]) {
            right--;
        }
        if (left < right) {
            //找到了，交换位置
            arr[base] = arr[right];
            arr[right] = center;
            base = right;
            left++;
        }
        while (left < right && center > arr[left]) {
            //找到了，交换位置
            left++;
        }
        if (left < right) {
            arr[base] = arr[left];
            arr[left] = center;
            base = left;
            right--;
        }
    }
    quick(arr, i, base - 1); //分别处理左右两侧了
    quick(arr, base + 1, j);
    return arr;
}
console.log(quickSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5]));
console.log(quickSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));


function quickSort( arr ) {
    if(arr.length <= 1) return arr;
    const num = arr[0];
    let left = [], right = [];
    for(let i = 1;i < arr.length; i++) {
        if(arr[i]<=num) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return quickSort(left).concat([num],quickSort(right));
}
console.log(quickSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5]));
console.log(quickSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));

参考链接：

https://www.imooc.com/article/73247

https://blog.csdn.net/xinxxxxxxxxx/article/details/123032933