快速排序的算法已经忘得干干净净，这次拿出来重温下，并用JS实现一次。
原理
先介绍下大致的排序步骤：
比如有这么一个数组：
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 5 | 7 | 1 | 4 | 3 |
以第一个值为基准值base=5，左侧的下标left=0，右侧的下标right=4。
（1）从右(right=4)开始找比5小的值，如果不符合就right--。发现3比5小，交换位置后
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 3 | 7 | 1 | 4 | 5 |
此时left=0，right=4。
（2）从左开始找比5大的值，如果不符合就left++。发现7比5大，交换位置后
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 3 | 5 | 1 | 4 | 7 |
此时left=1，right=4。到此一轮循环结束
（3）继续从下标right开始，由右向左寻找比5小的值，发现4比5小，交换位置后
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 3 | 4 | 1 | 5 | 7 |
此时left=1，right=3。
（4）继续从下标left开始，由左向右寻找比5大的值，直到left=right，也没有找到
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 3 | 4 | 1 | 5 | 7 |
此时left=3，right=3。到现在第一步就完成，基准值的左边都比它小，右边都比它大。然后分别对左右两侧的数组进行同样的操作即可。
实现
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;
}
完成了。
测试一波
quickSort([1,4,5,2,55,88,33,22]); //[1, 2, 4, 5, 22, 33, 55, 88]
quickSort([3,1,2,31,11,66,33,1]); // [1, 1, 2, 3, 11, 31, 33, 66]
quickSort([3,3,3,2,2,2,1,1,1]); //[1, 1, 1, 2, 2, 2, 3, 3, 3]
好了，如果有问题还望指出。
