分治法与快速排序

注：图片来源于文章（https://segmentfault.com/a/1190000015316531）快速排序采用了一种分治的思想，由于排序效率在同为O(N\*logN)的几种排序方法中效率较高，因此经常被采用。快速排序是一种不稳定的排序方法。该方法的基本思想是：

定基准：先从数列中取出一个数作为基准数；
分区：将比这个数打的数全放到它的右边，小于或等于它的数全放到它的左边；
再对左右两个区间重复第二步，直到各区间只有一个数（终止条件）。

上面三步中，第一步定基准的方式比较多样化，网上大体有三种方式（具体用哪一种个人觉得没啥差别）：

找数组中位于中间位置的一个数作为基准（参考文章后面的代码实现）；
直接选数组中第一个数作为基准；
取首尾中三个数的中位数作为基准（参考文章开头的图片）。

递归实现：

function quickSort(arr) {
  // 数组长度小于2就直接返回，不需要再处理了，这个就是快排的终止条件
  if (arr.length <= 1) {
    return arr;
  }

  // pivot意思是：枢纽、中心点
  var pivotIndex = Math.floor(arr.length / 2);
  // 找基准，并把基准从原数组中删除
  var pivot = arr.splice(pivotIndex, 1)[0];
  // 定义左右数组
  var left = [];
  var right = [];

  // 比基准小的放在left，比基准打的放在right
  arr.forEach(function (val) {
    if (val <= pivot) {
      left.push(val);
    } else {
      right.push(val);
    }
  });

  // 递归
  return quickSort(left).concat([pivot], quickSort(right));
}

分治法与快速排序 ​

分治法与快速排序