为什么当 quicksort 是 运行 数组大小 10^6 和元素大小 10^9 而不是合并排序时，为什么我会遇到 sigsegv 错误？

Question

我尝试了迭代方式并选择了枢轴元素作为数组的最后一个元素。我在 Hacker Earth 上执行它，它引发了 sigsegv 错误，其中数组大小从 1 到 10^6，数组元素大小从 1 到 10^9。 当我尝试归并排序时，它非常高效，甚至没有引发错误。这是怎么发生的？以下是实现的代码。

// An iterative implementation of quick sort        /* working*/
#include <iostream>
using namespace std;
void swap ( long int &a, long int &b )
{
    long int t = a;
    a = b;
    b = t;
}

int partition (int arr[],long int l,long int h)
{
    long int x = arr[h];
    long int i = l;
    long int j=h-1;
    while(i<j){
        if(arr[i]<x){
            i++;
        }
        if(arr[j]>x){
            j--;
            continue;
        }
        if(arr[i]>x&&arr[j]<x){
            swap(arr[i],arr[j]);
            i++;
            j--;
        }
    }
    swap(arr[i],arr[h]);
    return i;
}
void quickSortIterative (int arr[], int l, long int h)
{
    int stack[2];
    int top = -1;
    stack[ ++top ] = l; 
    stack[ ++top ] = h; 
    while ( top >= 0 )
    {
        h = stack[ top-- ];
        l = stack[ top-- ];
        long int p = partition( arr, l, h );
        if ( p-1 > l )
        {
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        }
        if ( p+1 < h )
        {
            stack[ ++top ] = p+1;
            stack[ ++top ] = h;
        }
    }
}

int main()
{
    long int N;
    cin>>N;
    long int i,j;
    int arr[N];
    for(i=0;i<N;i++){
        cin>>arr[i];
    }
    quickSortIterative( arr, 0, N - 1 );
    for ( i = 0; i < N; ++i ){
        cout<<arr[i]<<" ";
    }
    return 0;

}

Answer 1

在局部变量中分配大型数组是触发堆栈溢出的必经之路 — 典型执行环境中的堆栈根本无法处理此类事情。

您需要在堆上分配数组；例如通过使用 std::vector。您的代码也将更具可移植性，因为可变长度数组不是 C++ 标准的一部分。

Answer 2

stack[2]只有2个整数的空间，但代码"pushes"超过两个值入栈。考虑第一个循环，其中 p-1 > l && p+1 < h，在这种情况下，top 递增 4 次。您可以使用 push 和 pop 的等价物来使堆栈成为向量或堆栈来存储和加载值。

int arr[N] 对于大 N 也会失败。由于这是 C++，请考虑使用：

int * arr = new int[N];

你需要在 main 的末尾删除[] arr。