快速排序

快速排序（quick sort）是一种基于分治策略的排序算法。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

1. 随机选取一个数为基准数(这里选数组中间),初始化两个数组，一个存放比基准数小的元素，一个存放比基准数大的元素。
2. 循环这个数组,分别将小于大于基数的放到对应的数组里面。
3. 对左右两个数组分别进行递归调用。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  const pivot = arr[Math.floor(arr.length / 2)]
  const left = []
  const right = []
  for (let i = 0; i < arr.length; i++) {
    if (i === Math.floor(arr.length / 2)) continue
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i])
  }

  return quickSort(left).concat(pivot, quickSort(right))
}

参考

快速排序