c++ - C++ 中的快速排序实现(失败测试)

Question

我分配了一个用 C++ 实现 Quicksort 的任务，并且我已经成功地编写了看起来可行的代码。当我测试我的算法是否失败时，当我对一个包含一百万个元素的二进制文件中的数字进行排序时，它崩溃了。请注意，我有两个文件，每个文件都有一百万个元素。其中一个是未排序的，另一个是“几乎已排序”的，而我的算法似乎只有在对“几乎已排序”的文件进行排序时才会失败。这是我的代码的样子:

    int partition(int arr[], int low, int high) 
{
    int pivotI = low; //pivot index
    int pivot = arr[pivotI];
    int temp = arr[low];
    arr[low] = pivot;
    arr[pivotI] = temp;
    int partitionI = low;
    low++;
    while (low <= high)
    {
        if (arr[low] >= pivot)
        {
            if (arr[high] <= pivot)
            {
                temp = arr[high];
                arr[high] = arr[low];
                arr[low] = temp;
                low++;
            }
            high--;
        }
        else if (arr[high] <= pivot)
        {
            low++;
        }
        else
        {
            low++;
            high--;
        }
    }
    if (low == high)
    {
        if (arr[low - 1] < pivot)
        {
            temp = arr[low];
        }
        else
        {
            temp = arr[low - 1];
        }
    }
    else
    {
        temp = arr[high];
    }
    arr[high] = arr[partitionI];
    arr[partitionI] = temp;
    return high;
}

void quickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int p = partition(arr, left, right);
        quickSort(arr, left, p);
        quickSort(arr, p + 1, right);
    }
}

*当我运行所说的“几乎已排序”的二进制文件时，出现堆栈溢出错误。知道为什么会这样吗？谢谢

Answer 1

如果在快速排序中使用第一个值作为枢轴值，则已经排序的列表是最坏的情况，因为枢轴将始终是分区中的最低值。这可以大大增加递归深度。每个递归调用都需要栈帧空间(由参数、局部变量和返回地址组成)。对于几乎已排序的一百万个数字列表，您可能需要同时激活近一百万个堆栈帧。这很容易耗尽可用堆栈空间并产生错误。

您可以尝试不同的主元算法来解决这个问题，例如三的中位数。