S024手写快排★

快排像二分法一样都基于“分治”的算法思想，通过对数据进行分类处理，不断降低数量级，实现O(logN)（对数级别，比O(n)这种线性复杂度更低的一种，快排核心是二分法的O(logN)，实际复杂度为O(N*logN) ）的复杂度。

快速排序大概的流程是：

1、随机选择数组中的一个数A，以这个数为基准；

2、其他数字跟这个数进行比较，比这个数小的放在其左边，大的放在其右边；

3、经过一次循环之后，A左边为小于A的，右边为大于A的；

4、这时候将左边和右边的数再递归上面的过程。

var quickSort = function(arr) {
    if (arr.length <= 1) { return arr; }
    var pivotIndex = Math.floor(arr.length / 2);   //基准位置（理论上可任意选取）
    var pivot = arr.splice(pivotIndex, 1)[0];  //基准数
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++){
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));  //链接左数组、基准数构成的数组、右数组
};

2

function quickSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const cur = arr[arr.length - 1];
  const left = arr.filter((v, i) => v <= cur && i !== arr.length - 1);
  const right = arr.filter((v) => v > cur);
  return [...quickSort(left), cur, ...quickSort(right)];
}
// console.log(quickSort([3, 6, 2, 4, 1]));