快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。

它的基本思想很简单：先确定一个“基准点”（pivot），将所有小于“基准点”的值都放在该点的左侧，大于“基准点”的值都放在该点的右侧，然后对左右两侧不断递归这个过程，直到所有排序完成。

原理

假设是升序：

确定“基准点”（pivot）。虽然数组中任意一个值都能作为“基准点”，但通常是取数组的中间值。
建立两端的指针。左侧的指针指向数组的第一个元素，右侧的指针指向数组的最后一个元素。
左侧指针的当前值与“基准点”进行比较，如果小于“基准点”则指针向后移动一位，否则指针停在原地。
右侧指针的当前值与“基准点”进行比较，如果大于“基准点”则指针向前移动一位，否则指针停在原地。
左侧指针的位置与右侧指针的位置进行比较，如果前者大于等于后者，则本次排序结束；否则，左侧指针的值与右侧指针的值相交换。
对左右两侧重复第2至5步。

对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：

选择中间值“4”作为“基准点”。
第一个元素3小于4，左侧指针向后移动一位；第二个元素2小于4，左侧指针向后移动一位；第三个元素4等于4，左侧指针停在这个位置（数组的第2位）
倒数第一个元素1小于4，右侧指针停在这个位置（数组的第4位）
左侧指针的位置（2）小于右侧指针的位置（4），两个位置的值互换，数组变成 [3, 2, 1, 5, 4]
左侧指针向后移动一位，第四个元素5大于4，左侧指针停在这个位置（数组的第3位）
右侧指针向前移动一位，第四个元素5大于4，右侧指针移动向前移动一位，第三个元素1小于4，右侧指针停在这个位置（数组的第3位）
左侧指针的位置（3）大于右侧指针的位置（2），本次排序结束
对 [3, 2, 1]和[5, 4]两部分各自不断重复上述步骤，直到排序完成

实现

非原地算法

以第一个元素为基准点（也可以不是第一个元素），新建左右数组进行保存，不是原地算法，新增了一个数组来完成。

这里的思想跟上面的略有出入

新建两个左右数组来完成，大的放入右边，小的放入左边
然后继续对左右数组进行排序
最后拼接成新数组

function quickSort(arr) {
  if (arr.length === 0) return [];
  let left = [], right = [],
    pivot = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > pivot) {
      right.push(arr[i])
    } else {
      left.push(arr[i])
    }
  }
  return quickSort(left).concat(pivot, quickSort(right));
}

指针实现原地算法

以中间元素为基准

这个就是利用指针来实现的思路，这是一个原地算法。

先实现一轮排序的方法

// 传入原数组、需要处理的数组的开始位置、结束位置
function partition(arr, start, stop) {
  let pivot = Math.floor((start + stop) / 2),
    i = start,
    j = stop;
  while (i <= j) {
    while (arr[i] < arr[pivot]) {
      i++;
    }
    while (arr[j] > arr[pivot]) {
      j--;
    }
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
      j--;
    }
  }
  return i;
}

然后就是递归上面的过程，完成整个排序。

function quickSort2(arr, left, right) {
  if (arr.length < 2) return arr;
  left = (typeof left !== "number" ? 0 : left);
  right = (typeof right !== "number" ? arr.length - 1 : right);
  var index = partition(arr, left, right);
  if (left < index - 1) {
    quickSort(arr, left, index - 1);
  }
  if (index < right) {
    quickSort(arr, index, right);
  }
  return arr;
}