快速排序

1. 当数组只有一个元素时，该数组是有序的
2. 选取数组中间值 pivot，借助 splice，splice 会使原数组删除某些元素，并以数组的形式返回删除的元素。
3. 创建两个数组 left, right，分别存放小于等于中间值和大于中间值
4. 返回 quickSort(left).concat([pivot], quickSort(right))

Code

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let index = Math.floor(arr.length / 2);
  let pivot = arr.splice(index, 1)[0];
  let left = [];
  let right = [];
  for (let 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));
}