快速排序(快排)

快速排序的核心思想也是分治，将一个问题分解成多个子问题

在数据集之中，选择一个元素作为"基准"（pivot）

所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边

对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。，其重点在于数组的合并

Array.prototype.sort方法没有规定使用哪种排序算法，允许浏览器自定义，FireFox使用的是归并排序法，而 Chrome 使用的是快速排序法(大于22个数)
时间复杂度最优O(nlog(n)) 最差O(n^2)) 空间复杂度O(log(n))


function quickSort(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).concat(quickSort(right)) // concat参数可传key，也可传array
}

let res = quickSort([6, 7, 1, 4, 2, 3, 1])
console.log(res)

参考ruanyifengBlog

快速排序(快排) ​

快速排序(快排)