快速排序

React写多了，干啥都想用函数式，结果导致看快排看了一天还没弄清楚，最后原来不是生成新数组，是在原数组上进行排序啊！！！这样还省了空间，天哪真是越来越蠢了

闲话不多说，先上代码

function quickSort(array)  {
    quick(array, 0, array.length - 1);
}

function quick(array, left, right) {
    //  对数组长度为1的情况不作处理，减小时间
    if (array.length > 1) {
        //  对数组进行二分处理，并且返回刚才算出的中间值，因为中间值之前的肯定比中间值要小
        const pivot = partition(array, left, right);
        if (left < pivot - 1) {
            quick(array, left, pivot - 1);
        }
        if (right > pivot) {
          quick(array, pivot, right);
        }
    }
}

function partition(array, left, right) {
    const pivot = array[Math.floor((left + right) / 2))];
    let iL = left;
    let iR = right;
    while (iL <= iR) {
        while(array[iL] < pivot) iL++;
        while(array[iR] > pivot) iR--;
        if (iL < iR) {
            //  交换顺序，就不写了很简单
            swap(array, iL, iR);
            iL++;
            iR++;
        }
    }
    //  把上次计算的位置返回，用于做下次计算的分隔
    return iL;
}

快排比起归并排序稍微难理解一点

归并排序实质就是一个简单的递归，一个递归的方法将数组切成两半，切到一个元素为止，另外一个函数不断的合并排好序的数组，最终合并好，因为是有序数组，所以合并的会更快。
所以归并排序的精髓就是把两个小有序数组合成一个有序的大数组

快排实质是二分的策略，把数组根据一个中间值分隔成两份，中间值左边都比他小，右边都比他大，然后把中间值的位置返回，下一次对中间值的左边和右边的数组分别计算，直到数组长度为1时就不进行了。

做一次简单的分析

[ 3, 6, 4, 5, 2, 1]
中间值pivot是 Math.floor((0 + 5)/ 2, 10) = 2，就是array[2] = 4

值	步骤
pivot	中间值等于4
i=0	第一步 array[i] = 3 i < pivot 前进
i=1	第二步 array[i] = 6 i > pivot 停止
j=5	第三步 array[j] = 1 j < pivot 停止
交换	第四步 数组变为[3, 1, 4, 5, 2, 6]i, j 分别前进
i=2	第五步 array[i] = 4 i = pivot 停止
j=4	第六步 array[j] = 2 j < pivot 停止
交换	第七步 数组变为[3, 1, 2, 5, 4, 6] i, j 分别前进
i=3	第八步 array[i] = 5 停止
j=3	第九步 array[j] = 5 停止

第一次分隔完毕，返回中间值位置为4
以此类推

image.png