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
