快速排序算法原来这么简单

原理简述

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为（From Wikipedia）：

1. 从数列中挑出一个元素，称为"基准"（pivot）
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

简单实现

先上一个看起来巨简单的实现：

const quickSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }
  const left = arr.filter((e, i) => e < arr[0] && i !== 0);
  const right = arr.filter((e, i) => e >= arr[0] && i !== 0);
  return [...quickSort(left), arr[0], ...quickSort(right)];
  // return quickSort(left).concat([arr[0]], quickSort(right));
};

const arr = [15, 10, 6, 34, 21, 66, 32];
console.log(quickSort(arr));

解释起来就很方便，从数组里取出第0个元素作为基准数，然后过滤数组里的元素，比基准数小的，放到left，剩下的放right。当然，要排除第0个元素本身。最后将它们连接起来，两边各自递归下去。

作为算法呢，用了两次filter其实不太划算，但比这更重要的是，这个实现占用了额外的内存空间。

原地排序（in-place)

其实原理也不太难，每次递归，都是将我们的基准数放到它最终应该在的位置。

比如对于arr = [8, 10, 6, 34, 21, 66, 32]这样的数组，我们还是每次取第0个元素作为基准数。

初始状态：

NO.	Pivot	0	1	2	3	4	5	6
0	void	8	10	6	34	21	66	32

将第0个元素8作为基准数，并且把0号的位置挖出来，等待其他元素填入：

NO.	Pivot	0	1	2	3	4	5	6
0	void	8	10	6	34	21	66	32
1	8	void	10	6	34	21	66	32

从右边开始遍历，直到找到一个小于基准数8的6，将其放入0号坑位：

NO.	Pivot	0	1	2	3	4	5	6
0	void	8	10	6	34	21	66	32
1	8	void	10	6	34	21	66	32
2	8	6	10	void	34	21	66	32

这时再从左边开始遍历，直到找到一个大于基准数8的10，将其放入2号坑位：

NO.	Pivot	0	1	2	3	4	5	6
0	void	8	10	6	34	21	66	32
1	8	void	10	6	34	21	66	32
2	8	6	10	void	34	21	66	32
3	8	6	void	10	34	21	66	32

这时再从右边开始遍历，直到找到一个大于基准数8的……没了，那就说明1号坑位就是基准数8的窝了，将它填入：

NO.	Pivot	0	1	2	3	4	5	6
0	void	8	10	6	34	21	66	32
1	8	void	10	6	34	21	66	32
2	8	6	10	void	34	21	66	32
3	8	6	void	10	34	21	66	32
4	void	6	8	10	34	21	66	32

这时候要进入到递归了，我们已经将本次的基准数归位到1号位置了，那么接下来就是要排序arr[0]和arr[2..-1]，左边的就一个元素，刚好符合递归终止条件，直接return掉就可以了。右边还有五个元素，按照上述步骤继续递归下去就OK啦～

JavaScript(ES6) 代码实现：

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left >= right) {
    return;
  }

  let i = left;
  let j = right;

  // 取第一个值作为基准值
  let pivotVal = arr[left];

  // 取第一个位置作为坑位
  let blankIndex = left;

  while (i < j) {
    while (i < j && arr[j] >= pivotVal) {
      j -= 1;
    }
    if (i < j) {
      arr[blankIndex] = arr[j];
      blankIndex = j;
    }

    while (i < j && arr[i] <= pivotVal) {
      i += 1;
    }
    if (i < j) {
      arr[blankIndex] = arr[i];
      blankIndex = i;
    }
  }
  arr[blankIndex] = pivotVal;

  quickSort(arr, left, blankIndex - 1);
  quickSort(arr, blankIndex + 1, right);
};

const arr = [15, 10, 6, 34, 21, 66, 32];
quickSort(arr);
console.log(arr);

其中blankIndex和pivotVal是为了可读性添加的，为了节省点代码，也是可以省略掉的。比如两次判断，可以简化成下面这样，最后i和j相等，所以取哪个都可以。

while (i < j) {
  while (i < j && arr[j] >= arr[left]) {
    j -= 1;
  }
  if (i < j) {
    arr[i] = arr[j];
  }

  while (i < j && arr[i] <= arr[left]) {
    i += 1;
  }
  if (i < j) {
    arr[j] = arr[i];
  }
}
arr[i] = arr[left];
// arr[j] = arr[left];