对包含 15000 多个元素的数组进行排序时出现堆栈溢出异常

Question

这是我的快速排序算法实现。我收到 System.WhosebugException 消息 'Exception of type 'System.WhosebugException' was throwed.' 在尝试对大于 15k 元素的数组进行排序时。我实际上检查了 15000、19000、20000、30000 个元素，最后 3 个输入抛出异常。

private static int ArraySplitter(int[] intArr, int low, int high)
{
    int pivot = intArr[high];
    int lowIndex = (low - 1);
    for (int i = low; i < high; i++)
    {
        if (intArr[i] <= pivot)
        {
            lowIndex++;
            int temp = intArr[lowIndex];
            intArr[lowIndex] = intArr[i];
            intArr[i] = temp;
        }
    }
    int tempHigh = intArr[lowIndex + 1];
    intArr[lowIndex + 1] = intArr[high];
    intArr[high] = tempHigh;
    return lowIndex + 1;
}
private static void QSort(int[] intArr, int low, int high)
{
    if (low < high)
    {
        int index = ArraySplitter(intArr, low, high);
        QSort(intArr, low, index - 1);
        QSort(intArr, index + 1, high);
    }
}
public static void QuickSort(int[] intArr)
{
    QSort(intArr, 0, intArr.Length - 1);
}

我的 python 实现也因元素超过 5000 个的数组而中断。这是我的 python 代码 -

def QUICKSORT(arr, p, r):
    if p < r:
        q = PARTITION(arr, p, r)
        QUICKSORT(arr, p, q-1)
        QUICKSORT(arr, q+1, r)


def PARTITION(arr, p, r):
    x = arr[r]
    i = p-1
    for j in range(p, r-1):
        if arr[j] <= x:
            i = i + 1
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
    temp = arr[i+1]
    arr[i+1] = arr[r]
    arr[r] = temp
    return i+1

我遵循了 Thomas H Cormen 算法简介中的伪代码。

似乎是什么问题以及如何解决这个问题？

Answer 1

如果数据已经排序或反向排序，则选择 sub-array 中的第一个或最后一个元素作为主元会导致最坏情况 space 复杂度 O(n)。对于问题代码，在拆分之前将中间元素与最后一个元素 (array[high]) 交换，以处理已排序或反向排序的数据。还有其他模式会导致最坏情况下的行为。

仅对较小的分区使用递归会将堆栈 space 复杂度限制为 O(log(n))，但最坏情况下的时间复杂度仍为 O(n^2)。

private static void QSort(int[] intArr, int low, int high)
{
    while (low < high)
    {
        int index = ArraySplitter(intArr, low, high);
        if((index - low) <= (high - index)){
            QSort(intArr, low, index - 1);
            low = index + 1;
        } else {
            QSort(intArr, index + 1, high);
            high = index - 1;
        }
    }
}

对包含 15000 多个元素的数组进行排序时出现堆栈溢出异常

Getting Stack overflow Exception while sorting an array with 15000+ elements

c#

stack-overflow

recursion

exception

quicksort