使用随机基准的快速排序实现是否存在问题？大输入耗时波动大

const swap = (arr, i, j) => {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};

const partition = (arr, left, right) => {
  const pivot = arr[Math.floor(Math.random() * (arr.length - left) + left)];
  while (left <= right) {
    while (arr[left] < pivot) {
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }
    if (left <= right) {
      swap(arr, left, right);
      left++;
      right--;
    }
  }
  return left;
};

const quickSort = (arr, left, right) => {
  if (left === undefined) {
    left = 0;
    right = arr.length - 1;
  }
  if (left >= right) {
    return arr;
  }
  const pIndex = partition(arr, left, right);
  quickSort(arr, left, pIndex - 1);
  quickSort(arr, pIndex, right);
  return arr;
};

我用上面这个随机基准的快速排序实现总能得到正确结果，但测试发现处理大输入时运行时间波动极大。我猜是随机基准的问题，但不确定。作为排序算法新手，我在调试器里看了很久也没找到错误或疏漏，希望有人帮忙检查实现是否正确，而且我想保留随机基准的方案，不想换成中间元素之类的其他选择。

问题定位 #

你的实现能得到正确结果，但性能波动大的核心原因是随机基准的选取逻辑错误：
在partition函数中，你用arr.length - left计算随机范围，这会导致基准值可能取到当前处理的子数组（left到right区间）之外的元素。比如当处理left=5、right=10的子数组时，arr.length - left是整个数组长度减5，随机出来的索引可能超过10，取到数组后半段的元素。

这种错误会导致两种极端情况：

• 若选取的基准远大于当前子数组所有元素，分区后左半部分是整个子数组，右半部分为空，递归深度直接拉满到O(n)，时间复杂度退化为O(n²)
• 若基准远小于当前子数组所有元素，分区后右半部分是整个子数组，同样导致性能暴跌

虽然最终排序结果正确，但这种随机基准的“错位选取”会让算法的时间稳定性完全失效，大输入下自然出现剧烈的时间波动。

修正方案（保留随机基准） #

只需要把基准选取的范围从整个数组，改成当前处理的left到right子数组即可，修正后的partition函数如下：

const partition = (arr, left, right) => {
  // 修正：在left到right的范围内随机选基准索引
  const pivotIndex = Math.floor(Math.random() * (right - left + 1) + left);
  const pivot = arr[pivotIndex];
  while (left <= right) {
    while (arr[left] < pivot) {
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }
    if (left <= right) {
      swap(arr, left, right);
      left++;
      right--;
    }
  }
  return left;
};

额外优化建议（可选） #

如果想进一步提升稳定性，可以在选取随机基准后，先把基准元素和子数组的右端（或左端）元素交换，再用经典的分区逻辑处理——不过这不是必须的，只要修正了基准选取的范围，性能波动的问题就会解决。

内容的提问来源于stack exchange，提问作者fishgas