思想
img
转自《坐在马桶上看算法：快速排序》,作者见图
实现
function quick2(array, left, right) {
if (left > right) {
return;
}
let temp = array[left]; //temp中存的就是基准数
let i = left;
let j = right;
let t = 0
while (i != j) { //顺序很重要，要先从右边开始找, 因为基准在最左边
while (array[j] >= temp && i < j){
j--;
}
while (array[i] <= temp && i < j){//再找右边的
i++;
}
if (i < j)//交换两个数在数组中的位置
{
t = array[i];
array[i] = array[j];
array[j] = t;
}
console.log(i, j);
}
//最终将基准数归位
array[left] = array[i];
array[i] = temp;
quick2(array, left, i - 1);//继续处理左边的，这里是一个递归的过程
quick2(array, i + 1, right);//继续处理右边的 ，这里是一个递归的过程
}
let array = [6 , 1, 2 ,7 , 9 , 3 ,4 ,5, 10 , 8]
quick2(array, 0, array.length - 1)
console.log(array);
