特性：

排序方法 时间复杂度 空间复杂度 稳定性
快速排序 O(nlogn) O(logn) 不稳定

和归并排序的对比

快速排序 归并排序
特点 两个子数组都有序时，则整个数组也就自然有序了 将数组分成两个子数组分别排序，并将有序的子数组归并
切分 取决于数组的内容 等分两半

思路：

选取一个“切分“点，确保：

  1. 切分点的左侧都小于它。
  2. 切分点的右侧都大于它。
  3. 分别对切分点进行排序

过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

特点：将一个数组分成两个子数组，将两部分独立排序。

伪代码：

  1. function quickSort(a, lo, hi) {
  2.   if (hi <= lo) return;
  3.   const j = partition(a, lo, hi); // 切分，快速排序的关键
  4.   quickSort(a, lo, j - 1);
  5.   quickSort(a, j + 1, hi);
  6. }

切分

  1. const { less, exch } = require('./util');
  3. function partition(a, lo, hi) {
  4.   let i = lo;
  5.   let j = hi + 1;
  6.   // 随意选取a[lo]做为切分元素
  7.   const v = a[lo];
  9.   while(1) {
  10.     // 从数组的左端开始向右扫描，直到寻找到一个大于等于v的元素
  11.     while(less(a[++i], v])) if(i === hi) break;
  12.     // 从数组的右端开始向左扫描，直到寻找到一个小于等于v的元素
  13.     while(less(v, a[--j])) if (j === lo) break;
  14.     // 边界条件：如果指针相遇，则退出循环
  15.     if(i >= j) break;
  16.     // 调换他们的位置，一定可以找到，如果找不到则在上一步终止了
  17.     exch(a, i, j);
  18.   }
  19.   // 交换v和指针相遇位置的值
  20.   exch(a, lo, j);
  21.   return j;
  22. }

实现

  1. const { less, exch, getArr } = require('../utils');
  3. function partition(arr, lo, hi) {
  4.   let i = lo;
  5.   let j = hi + 1;
  6.   // 随意选取一个作为“切分”点
  7.   const v = arr[lo];
  9.   while (1) {
  10.     // 从左到右寻找到大于 v 的值（下标）
  11.     while (less(arr[++i], v)) {
  12.       if (i === hi) break;
  13.     }
  14.     // 从右到左寻找到小于 v 的值（下标）
  15.     while (less(v, arr[--j])) {
  16.       if (j === lo) break;
  17.     }
  18.     // 如果指针（下标）对撞则终止循环
  19.     if (i >= j) break;
  20.     // 交换小的值
  21.     exch(arr, i, j);
  22.   }
  23.   exch(arr, lo, j);
  24.   return j;
  25. }
  27. function quickSort(arr, lo, hi) {
  28.   if (lo === undefined) {
  29.     lo = 0;
  30.     hi = arr.length - 1;
  31.   }
  32.   if (lo >= hi) return;
  33.   const j = partition(arr, lo, hi); // 获取切分点
  34.   quickSort(arr, lo, j - 1);
  35.   quickSort(arr, j + 1, hi);
  36.   return arr;
  37. }

算法改进

切换到插入排序

小数组使用使用插入排序吧，长度在5-15内用这个，很快；

三取样切分

使用子数组的一小部分元素的中位数来切分数组，代价是需要计算中位数。

三向切分的快速排序

针对重复数据比较多的数组。

  1. function quick3way(a, lo, hi) {
  2.     if (hi <= lo) return;
  3.   let lt = lo; // a[lo, ...lt - 1]中的所有元素都小于v
  4.   let gt = hi; // a[gt + 1, ...hi]中的所有元素都大于v
  5.   let i = lo + 1; // a[lt, ...i]中的所有元素都等于v
  6.   // a[i, ...gt] 中的元素还未确定
  7.   let v = a[lo];
  9.   while(i <= gt) {
  10.     let cmp = a[i] - v;
  11.     // a[i] < v，交换 a[lt] 和 a[i]，lt指针、i指针右移，将小于v的都放到v的右边
  12.     if (cmp < 0) exch(a, lt++, i++);
  13.     // a[i] > v，交换 a[i] 和 a[gt]，gt左移，将大于v的都迁移到v的右边
  14.     else if (cmp > 0) exch(a, i, gt--);
  15.     // 相等情况移动i指针
  16.     else i++
  17.   }
  18.   sort(a, lo, lt - 1);
  19.   sort(a, gt + 1, hi);
  20. }