javascript - QuickSort 算法因 stackoverflow 错误而失败

Question

我尝试从Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein - 算法导论，第三版 - 2009 年 * 第 7.1 节

在 JavaScript 中。

所以这是我的实现:

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

function partition(arr, left = 0, right = arr.length - 1) {
    let pivot = arr[right];
    let i = left - 1;
    let j;

    for (j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }

    swap(arr, i + 1, right);
    return i + 1;
}

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

如果我传递长度 > 10 000 的已排序数组，此代码会因计算器错误而失败

如果我传递具有完全随机整数的数组 - 即使有 50 000 个元素，一切都按预期工作。所以我不明白是我的代码有问题，还是我的 Node 无法处理如此大的调用堆栈以用于最坏情况下的快速排序使用。

Answer 1

有了足够大的数组，您最终将达到最大堆栈大小并获得该异常。您之前在排序数组中看到它的原因是因为您选择枢轴的方式。

您已将枢轴作为数组的最后一个元素来实现它，这恰好意味着最坏的情况发生在您获得排序数组时。您的主元值始终是最大值(如果按相反方向排序则为最小值)，因此每个元素都小于主元，没有一个大于主元。因此，与其将数组拆分为两个大致相等的子数组，不如将其拆分为一个子数组，该子数组的元素只比开始时少一个。

选择枢轴以避免这种情况的一种方法是随机选择枢轴。这使得它不太可能(但并非不可能)达到最坏的情况，因此平均来说效果很好。它确实有一个漏洞，如果有人知道您正在使用的随机数算法和种子，那么他们可以制作一个数组，这将迫使您进入最坏的情况。

理想的支点是中值。因此，一种方法是尝试找到中位数或接近中位数。例如，您可以从数组的 3 个随机元素中抽取样本，并使用这 3 个元素的中值作为您的基准。这不太可能正好是中位数，但在大多数情况下已经足够好了。您可以进行更多采样以获得更好的中位数近似值，但是您将花费更多时间来尝试找到枢轴，而不仅仅是继续使用算法；这是一个权衡。