排序算法全解，为什么快排的时间波动特别大？

// 简洁，但并非原地快排
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x <= pivot);
  const right = arr.slice(1).filter(x => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}



// 原地快排
function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // 获取分区索引：pivot 已放在正确位置
    const pivotIndex = partition(arr, low, high);

    // 递归排序 pivot 左右两部分
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr; // 为了链式调用方便，可选
}

// 分区函数
function partition(arr, low, high) {
  const pivot = arr[high]; // 选最后一个元素为 pivot
  let i = low; // i 表示小于等于 pivot 区域的边界

  for (let j = low; j < high; j++) {
    // 如果当前元素 <= pivot，就把它放到左边区域
    if (arr[j] <= pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
      i++; // 边界右移
    }
  }

  // 最后把 pivot（arr[high]）放到它该在的位置
  [arr[i], arr[high]] = [arr[high], arr[i]];
  return i; // 返回 pivot 的最终位置
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  let result = [], i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

function heapSort(arr) {
  const n = arr.length;

  // 构建大顶堆，从最后一个非叶子节点开始
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 依次取出堆顶元素，放到数组末尾
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 交换堆顶与当前尾部
    heapify(arr, i, 0); // 重新对堆顶元素调整堆
  }

  return arr;
}

// 维护大顶堆的堆化过程
function heapify(arr, heapSize, rootIndex) {
  let largest = rootIndex;
  const left = 2 * rootIndex + 1;
  const right = 2 * rootIndex + 2;

  // 找出三个节点中最大的那个
  if (left < heapSize && arr[left] > arr[largest]) largest = left;
  if (right < heapSize && arr[right] > arr[largest]) largest = right;

  // 如果最大值不是根节点，交换并递归堆化
  if (largest !== rootIndex) {
    [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]];
    heapify(arr, heapSize, largest);
  }
}

// 示例
const arr = [4, 10, 3, 5, 1];
console.log(heapSort(arr)); // 输出: [1, 3, 4, 5, 10]