Qucksort获得了100000个元素的StackoverFlowerRor，但Mergesort不在Java中

Question

根据此帖子：

堆栈溢出的常见原因是一个不良的递归调用。

那么为什么它以10000个元素运行，但要获得100000个元素的stackoverflowerror？

QuickSort ：

public static void quicksort(int[] data, int low, int high) {
    if (low < high) {
        int p = partition(data, low, high);
        quicksort(data, low, p);
        quicksort(data, p + 1, high);
    }
}
public static int partition(int[] data, int low, int high) {
    int pivot = data[low];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        do {
            i++;
        } while (data[i] < pivot);
        do {
            j--;
        } while (data[j] > pivot);
        if (i >= j)
            return j;
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

Mergesort ：

public static void mergesort(int[] data, int left, int right) {
    if (left < right){
        int middle = (left + right) / 2;
        mergesort(data, left, middle);
        mergesort(data, middle+1, right);
        merge(data, left, middle, right);
    }
}
private static void merge(int[] data, int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;
    int[] dataLeft = new int[n1];
    int[] dataRight = new int[n2];
    for (int i = 0; i < n1; i++)
        dataLeft[i] = data[left+i];
    for (int i = 0; i < n2; i++) 
        dataRight[i] = data[middle+1+i];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (dataLeft[i] <= dataRight[j]) {
            data[k] = dataLeft[i];
            i++;
        }
        else {
            data[k] = dataRight[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        data[k] = dataLeft[i];
        i++;
        k++;
    }
    while (j < n2) {
        data[k] = dataRight[j];
        j++;
        k++;
    }
}

对于Mergesort，它运行良好。

原因是什么？有人请解释吗？

Answer 1

此行为对于使用Pivot int pivot = data[low];选择并分类（或大部分）阵列的选定分区方案可以期待此行为 - 在这种情况下，堆栈深度可能到达N=length of array。

。

您必须了解更多明智的枢轴选择-median of three或random pivot index。这些方法减少了特殊数据集的不良行为的可能性（但不要完全摆脱）

第二步 - 优化递归方案：

要确保最多使用O（log n）空间，请首先重新浏览 分区的较小一侧，然后使用尾部呼叫重复 另一个。 因此，只需比较(p-low)和high-p，然后选择这些呼叫的正确顺序：

    quicksort(data, low, p);
    quicksort(data, p + 1, high);

这些问题和更多解决方案在Wiki页面上很快就会详细说明 - 在任何算法书/课程

中

请注意，Mergesort始终提供最大的堆栈深度日志（N）