快速排序 - javascript

快速排序简称快排，分而治之的经典应用；
时间复杂度，最差的情况下，则数组按顺序倒叙则时间复杂度为O(n^2)，平均时间复杂度O(nlogN)
空间复杂度O(n),平均空间复杂度O(logN)
快速排序是一种时间复杂度不稳定的算法，一般情况下它的时间复杂度为O(nlogn)，但在极端条件下会退化为O(n2)。
动图：

1. 选取privot(基点)作为基准值；从数组右边开始往前搜索，如果小于基准值；停止
2. 从数组左边开始搜索，如果大于基准值；停止
3. 交换双方位置；继续如上；
4. 如果搜索到最后。右边index==左边index，则将基准值与最后的值互换；第一次查询交换全部完成；
5. 基于随后的搜索index，则第一次查询交换全部完成的index，将数组分为两边，分别递归；递归执行操作继续如上

    function quickSort2(arr, start, end) {
        let len = arr.length;
        // start和end如果查找的时候传入的是同一个或者end大于start则停止寻找；
        if (start >= end) {
            // console.log("停止查找", start, end);
            return
        }
        let i = start;
        let j = end;
        //基准点
        let tarGet = arr[start];
        // 因为要对i和j进行搜寻操作，即start从左往右，end从右往左；需要一个值去承载--或++用来判断条件等;
        if (i < j) {
            while (i < j) {
                //从右边到左边end的j搜索比目标小的
                while (arr[j] > tarGet && i < j) {
                    j--
                }
                //从左边到右边start的j搜索比目标大的
                while (arr[i] <= tarGet && i < j) {
                    i++
                }
                // i和j都停止搜索,如果i和j的位置不相同(则表示搜索未结束);调换相互的位置；
                if (i < j) {
                    let temp = arr[i]
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        // 当所有循环操作结束后，说明i和j搜索最后的目标都是一样的，，最后搜索出来的下标元素和target调换；
        arr[start] = arr[i];
        arr[i] = tarGet;
        // 然后分割左右递归
        // 将左边的分割
        // console.log('分割左边,开始-结束', start, i-1);
        quickSort2(arr, start, i - 1)
        // console.log('分割右边,开始-结束', i+1, end);
        quickSort2(arr, i + 1, end)

        // return       
    }```
    console.time()
     quickSort3(arr, 0, arr.length - 1)
    console.log(arr);
    console.timeEnd()