题目描述

请实现快速排序

测试用例

输入：[0,-1,1,-2,2] 输出：[-2,-1,0,1,2]

代码实现

let arr = [5, 3, 6, 7, 4, 1, 0, 2, 9, 10, 8];

let quickSort = (arr, left, right) => {
    

    // 第一个值为基准
    // 把第一个值拿出去，位置空出来，也就是l或者r此时的位置
    
    if(left < right){
        let l = left;
        let r = right;
        let pivot = arr[l];
        // 先从后往前找比pivot小的值
        while(l < r){
            while(l < r && arr[r] >= pivot){
                r --;
            }
        // 找到了，把它放到空出来的位置
            if(l < r){
                arr[l] = arr[r];
                l ++;
            }
        

        // 再从前往后找
            while(l < r && arr[l] <= pivot){
                l ++;
            }
            if(l < r){
                arr[r] = arr[l];
                r --;
            }
        }

        // 最后空出来的位置就是pivot的位置
        arr[l] = pivot;
        // 分别递归pivot两边的子数组
        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    }
};
quickSort(arr, 0, arr.length - 1);
console.log(arr);
/*
[
   0, 1, 2, 3, 4,
   5, 6, 7, 8, 9,
  10
]
*/