快速排序

归纳公式

**

转公式为代码

const quickSort = (a) => {
  const [pivot, ...rest] = a;
  return (a.length <= 1) 
            ? a 
            : [ 
                ...quickSort(rest.filter((i) => i <= pivot)),
                pivot,
                ...quickSort(rest.filter((i) => i > pivot)) 
              ]
}

优化：减少遍历（一次遍历多做事），减少复制（就地操作）
https://jsbin.com/fuvacosaxe/1/edit?js,console
https://jsbin.com/fuvacosaxe/2/edit?js,console

const swap = (a, i, j) => [a[i], a[j]] = [a[j], a[i]];
const handlePivot = (a, start, end) => {
  if (end - start === 0) return -1;
  if (end - start === 1) return 0;
  const pivot = a[start];
  let smallEnd = start, bigStart = end, i = start + 1;
  while(bigStart - smallEnd > 1) {
    console.log(`smallEnd ${smallEnd} bigStart ${bigStart}`)
    console.log(`${a[i]}, pivot ${pivot} i ${i}`)
      if(a[i] > pivot) {
      bigStart -= 1;
      swap(a, i, bigStart)
    } else {
      smallEnd += 1;
      swap(a, i, smallEnd);
      i += 1;
    }
  }
  console.log(a)
  swap(a, start, smallEnd)
  console.log(a)
  return smallEnd;
}
const quickSort = (a) => quickSortArray(a, 0, a.length);
const quickSortArray = (a, start, end) => {
  if (end - start <= 1) return a;
  const pivotIndex = handlePivot(a, start, end);
  quickSortArray(a, start, pivotIndex);
  quickSortArray(a, pivotIndex + 1, end);
  return a;
}
console.log('------------', quickSort([2, 1, 3, 1, 4]))