重学JS（十三）—— js实现快速排序

快速排序的算法已经忘得干干净净，这次拿出来重温下，并用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]

好了，如果有问题还望指出。