快速排序

时间复杂度：O(NlogN)

空间复杂度：O(logN)

核心：根左右

快排思想

快速排序主要使用递归分支的思想，选出基准值，通过一趟排序，将待排数据分隔成两部分。

其中左分区均比右分区的数小，则可以分别对这两个分区继续进行排序，以达到整个序列有序。

快排、插排比较

值得一提的是，当 n 足够小的时候，快排优势变小。

事实上插排经优化后对于小数据集的排序性能可以超过快排。

对于插排和快排，理论上的平均时间复杂度分别为 O(n^2)和 O(nlogn)。

插排在数组已经有序时的时间复杂度是 O(n)，快排在数组已经有序时会退化到 O(n^2)。

性能瓶颈

因为快速排序的性能瓶颈在于递归的深度，

最坏的情况是每次的哨兵都是最小元素或者最大元素，

那么进行分区（一边是小于哨兵的元素，另一边是大于哨兵的元素）时，就会有一边是空的，不能发挥分区对数化的效果。

如果这么排下去，递归的层数就达到了n, 而每一层的复杂度是O(n)，因此快排这时候会退化成O(n^2)级别。

V8 中的 sort

github.com/v8 sort 源码 (opens new window)

查阅源码我们可以发现，对于需要排序的元素个数 n，具体排序策略有几下中情形：

• 当 n<=10 时，采用插入排序；
• 当 n>10 时，采用三路快速排序；
• 10<n <=1000，采用中位数作为哨兵元素；
• n>1000，每隔 200~215 个元素挑出一个元素，放到一个新数组中，然后对它排序，找到中间位置的数，以此作为中位数。

实现

以升序快速排序为例：

1. 分区
   • 从数组中任意选择一个元素作为基准，所有比基准小的元素放在基准前面，比基准大的元素放在基准后面。
2. 递归
   • 递归地对基准前后的子数组进行分区操作

// 快排 == 二叉树前序遍历，根左右
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; //递归出口
  }
  let left = [],
    right = [],
    current = arr.splice(0, 1);
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < current) {
      left.push(arr[i]); //放在左边
    } else {
      right.push(arr[i]); //放在右边
    }
  }
  return quickSort(left).concat(current, quickSort(right));
}

console.log(quickSort([1, 5, 3, 2, 14, 6, 2, 3, 4, 5, 6, 7]));