带你读《图解算法小抄》十四、排序（10）

function getRandomPivot(arr, start, end) {
  const randomIndex = Math.floor(Math.random() * (end - start + 1)) + start;
  [arr[randomIndex], arr[end]] = [arr[end], arr[randomIndex]];
  return partition(arr, start, end);
}
function quickSortRandomPivot(arr, start = 0, end = arr.length - 1) {
  if (start < end) {
    const pivotIndex = getRandomPivot(arr, start, end);
    quickSortRandomPivot(arr, start, pivotIndex - 1);
    quickSortRandomPivot(arr, pivotIndex + 1, end);
  }
  return arr;
}

function getMedianOfThree(arr, start, end) {
  const mid = Math.floor((start + end) / 2);
  if (arr[start] > arr[mid]) {
    [arr[start], arr[mid]] = [arr[mid], arr[start]];
  }
  if (arr[start] > arr[end]) {
    [arr[start], arr[end]] = [arr[end], arr[start]];
  }
  if (arr[mid] > arr[end]) {
    [arr[mid], arr[end]] = [arr[end], arr[mid]];
  }
  return mid;
}
function quickSortMedianOfThree(arr, start = 0, end = arr.length - 1) {
  if (start < end) {
    const pivotIndex = getMedianOfThree(arr, start, end);
    const pivot = arr[pivotIndex];
    let left = start;
    let right = end - 1;
    while (left <= right) {
      while (arr[left] < pivot) {
        left++;
      }
      while (arr[right] > pivot) {
        right--;
      }
      if (left <= right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
      }
    }
    [arr[left], arr[pivotIndex]] = [arr[pivotIndex], arr[left]];
    quickSortMedianOfThree(arr, start, left - 1);
    quickSortMedianOfThree(arr, left + 1, end);
  }
  return arr;
}