// 快速排序
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(pivot, quickSort(right));
}

console.time('quickSort');
console.log(quickSort([0, 1, 0, 2, 0, 2, 1, 0, 1]));
console.timeEnd('quickSort');

/* 
  三路排序算法
*/
function threeWaySort(arr) {
  let zero = 0,
    two = arr.length - 1;
  for (let i = 0; i < arr.length; i++) {
    while (arr[i] === 2 && i < two) {
      [arr[i], arr[two]] = [arr[two], arr[i]];
      two--;
    }

    if (arr[i] === 0) {
      [arr[i], arr[zero]] = [arr[zero], arr[i]];
      zero++;
    }
  }

  return arr;
}

console.time('threeWaySort');
console.log(threeWaySort([0, 1, 0, 2, 0, 2, 1, 0, 1]));
console.timeEnd('threeWaySort');