快速排序堆栈溢出 C++ 大数

Question

美好的一天我正在尝试对 10000 个数字使用快速排序，但它给我堆栈溢出错误。它适用于随机数，但不适用于递减和递增的数字。

' 谢谢

void quickSort(long* array, long start, long last)
{
    if (start < last)
    {
        int p = partition(array, start, last);
        quickSort(array, start, p-1);
        quickSort(array, p + 1, last);
    }
}
int partition(long* array, long start, long last)//first partition
{
    int j = start + 1;
    for (long i = start + 1;i <= last;i++)
    {
        if (array[i] < array[start])
        {
            swap(array[i], array[j]);
            j++;
        }           

    }
    swap(array[start], array[j - 1]);
    return j - 1;
}
'

Answer 1

对于已排序的元素，您可以通过选择 array[start]、array[last] 和 array[(start + last + 1)/2] 这三个元素的中位数作为枢轴值来避免此问题。

int median_of_3(long* array, long start, long last)
{
    long a = (start + last + 1)/2, b = start, c = last;
    if (array[c] < array[a]) swap(array[c], array[a]);
    if (array[b] < array[a]) swap(array[b], array[a]);
    if (array[c] < array[b]) swap(array[c], array[b]);
    return partition(array, start, last);
}

另一种避免大堆栈深度的策略是计算哪个分区较小，并递归调用较小的分区。然后可以将另一个分区优化成一个循环（尾递归优化）。

void quickSort(long* array, long start, long last)
{
    if (start >= last) return;

    int p = median_of_3(array, start, last);
    int next_start[2] = { start, p + 1 };
    int next_last[2] = { p - 1, last };
    bool i = p > (start + last)/2;
    quickSort(array, next_start[i], next_last[i]);
    /*
     * If the compiler does not optimize the tail call below into
     * a loop, it is easy to do the optimization manually.
     */
    quickSort(array, next_start[!i], next_last[!i]);
}

内省也可以用来避免大的堆栈深度。你跟踪你的递归调用深度，如果它是 "too deep"，你就会安全地进入不同的排序策略，比如合并排序或堆排序。这是 std::sort.

当前使用的行为

void introSortImpl(long* array, long start, long last, int depth)
{
    if (--depth == 0) {
        heapSort(array, start, last);
        return;
    }

    if (start >= last) return;

    int p = median_of_3(array, start, last);
    int next_start[2] = { start, p + 1 };
    int next_last[2] = { p - 1, last };
    bool i = p > (start + last)/2;
    introSortImpl(array, next_start[i], next_last[i], depth);
    introSortImpl(array, next_start[!i], next_last[!i], depth);
}

void introspectionSort(long* array, long start, long last)
{
    introSortImpl(array, start, last, log2(start - last) * 3);
}

Answer 2

代码没问题，但您的编译器使用堆栈的效率很低。您只需要提高保留的筹码量。它在调试配置文件中比在发布配置文件中更频繁地发生，因为编译器保留大堆栈块以检查堆栈是否在执行过程中被破坏。

Answer 3

Lomuto 分区方案的示例，如快速排序，在较小的分区上使用递归，更新 l 或 r，然后循环返回以将较大的分区分成两个分区，重复该过程。最坏情况堆栈 space 是 O(log2(n)) ，这应该避免堆栈溢出。最坏情况下的时间复杂度仍然是 O(n^2)（取决于分区的实现方式）。

有些人称这个例子为半递归。这不是尾递归的例子，因为尾递归意味着递归函数在调用自身之后只是returns。原题例子中的第二次调用是尾调用

void quicksort(int * tab, int l, int r)
{
   int q;
   while(l < r)
   {
      q = partition(tab, l, r);
      if(q - l < r - q) {     // recurse into the smaller partition
         quicksort(tab, l, q - 1);
         l = q + 1;
      } else {
         quicksort(tab, q + 1, r);
         r = q - 1;
      }
   }                          // loop on the larger partition
}

快速排序堆栈溢出 C++ 大数

QUICK SORT stack overflow c++ big numbers

c++

sorting

stack

quicksort