C++ 中的快速排序实现（失败测试）

Question

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

    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);
    }
}

*当我运行说 "almost sorted" 二进制文件时出现堆栈溢出错误。知道为什么会这样吗？谢谢

Answer 1

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

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

Answer 2

避免堆栈溢出的一种方法是结合使用循环和递归。在每个 partition() 之后的 quicksort() 中，检查是否 (p - left) <= (right - p - 1)，并且只对较小的部分使用递归，然后循环返回以拆分较大的部分。这将最坏情况下的堆栈开销限制为 log2(n)。不过，最坏情况的时间复杂度仍为 O(n^2)。

使用中位数的中位数可以将最坏情况下的时间复杂度降低到 O(n log(n))

http://en.wikipedia.org/wiki/Median_of_medians

但是常数因子 factor 更大，减慢了平均和最佳情况的快速排序。

C++ 中的快速排序实现（失败测试）

Quick Sort Implementation (Test for failure) in C++

c++

stack-overflow

sorting

algorithm

quicksort