工作原理

使用分治法来把一个序列分为两个子序列，然后递归地排序这两个子序列。
快速排序步骤为：

挑选基准值：从数列中挑出一个元素，称为“基准”。
分割：重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面。在这个分割结束之后，对基准值的排序就已经完成。
递归排序子序列：分别递归地将小于和大于基准值元素的子序列排序。

js代码实现 + 效率测试

运算10次，平均耗时19.58 ms

  1. // 创建 20000 个随机数，数值范围：1 - 100000
  2. let ary = [];
  3. for (let i = 0; i < 20000; i++) {
  4.   ary.push( Math.floor( Math.random()*99999 + 1 ) );
  5. }
  7. // 快速排序 基准默认总是取当前区间的最后一个元素
  8. function quickSort(ary, start, end) {
  9.   let _quickSort = function(ary, start, end) {
  10.     if (end <= start) {
  11.       return ;
  12.     }
  14.     let pivot = ary[end],
  15.         left = start,
  16.         right = end - 1;
  18.     while (left < right) {
  19.       while (ary[left] < pivot && left < right) left++;
  20.       while (ary[right] >= pivot && left < right) right--;
  21.       [ary[left], ary[right]] = [ary[right], ary[left]];
  22.     }
  24.     if (ary[left] >= pivot) {
  25.       [ary[left], ary[end]] = [ary[end], ary[left]];
  26.     }
  27.     else {
  28.       left++;
  29.     }
  31.     _quickSort(ary, start, left - 1);
  32.     _quickSort(ary, left + 1, end);
  33.   }
  34.   _quickSort(ary, start, end);
  35. }
  36. console.time( '快速排序' );
  37. quickSort(ary, 0, ary.length - 1);
  38. console.timeEnd( '快速排序' );