比较函数

function less(a, b) { return a - b;}
function greater(a, b) { return b - a; }

随机化分区

function partition(arr, l, r, comp = less) {
  swap(arr, r, Math.floor(Math.rand()*(r - l) + l));
  return partition_right(arr, l, r, comp);
}

右边界分区

function partition_right(arr, l, r, comp = less) {
  let x = arr[r];
  let i = l, j = l;
  while (j < r) {
    if (comp(arr[j], x) <= 0) {
      i++;
        }
    j++;
  }
  swap(arr, i, r);
  return i;
}

三分区

function partition(arr, l, r, comp = less) {
  if (l + 1 >= r) return;
  let x = arr[l];
  let i = l;
  while (i < r) {
    if (comp(arr[i], x) === 0) {
      i++;
    } else if (comp(arr[i], x) > 0) {
      --r;
      swap(arr, i, r);
        } else if (comp(arr[i], x) < 0) {
      swap(arr, i, l);
      i++;
      l++;
    }
  }
  return l;
}