思想

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);