Quicksort引起堆栈溢出？

这是我实现快速排序的：Quicksort引起堆栈溢出？

int choosePivotIndex(int l, int r) 
{ 
    return l + rand() % (r + 1 - l); 
} 

void swap(int a[], int l, int r) 
{ 
    int tmp = a[l]; 
    a[l] = a[r]; 
    a[r] = tmp; 
} 

int partition(int a[], int l, int r) 
{ 
    int p = choosePivotIndex(l, r); 
    swap(a, p, r); 
    int d = l; 
    for (int i = l ; i < r ; ++i) 
    { 
     if (a[i] < a[r]) 
     { 
      swap(a, i, d); 
      ++d; 
     } 
    } 
    swap(a, d, r); 
    return d; 
} 

void quickSort(int a[], int l, int r) 
{ 
    if (l < r) 
    { 
     int p = partition(a, l, r); 
     quickSort(a, l, p - 1); 
     quickSort(a, p + 1, r); 
    } 
} 

void quickSort(int a[], int len) 
{ 
    srand(static_cast<unsigned int>(time(nullptr))); 

    quickSort(a, 0, len - 1); 
}

我用它像这样：

int a[10]; 
quickSort(a, 10);

它似乎做工精细的小型阵列，但是当我给它提供一个大的（如300 000元素）我得到一个堆栈溢出错误。我试图通过使用只在小部分递归和排序在while循环更大一个补救：

void quickSort(int a[], int l, int r) 
{ 
    while (l < r) 
    { 
     int p = partition(a, l, r); 
     if (p - l < r - p) 
     { 
      quickSort(a, l, p - 1); 
      l = p + 1; 
     } 
     else 
     { 
      quickSort(a, p + 1, r); 
      r = p - 1; 
     } 
    } 
}

，但我得到了相同的结果。我做错了什么？我如何才能使它适用于更大的阵列？

来源

2017-10-05 NPS

来在堆上声明它们：较大阵列的内存是堆栈还是堆？ –

看来你是通过值传递数组，而不是通过引用。我不确定这是否是由设计决定的，但是具有30万个元素的阵列，您将很快耗尽堆栈空间。 – Baldy

@Baldy，你不能通过值传递c数组，a []参数总是与相应的指针相同... –

按照评价的讨论部分中的代码看起来是良好和有问题的部分将是堆

int a[10];

如果是这种细为较小的阵列在阵列的声明其容易跑到大数组的堆栈溢出，为了测试这个，你可以声明一大堆int a[1000000]，如果没有快速排序代码，你仍然会得到堆栈溢出。因此，建议通过执行new

来源

2017-10-05 15:55:58

Quicksort引起堆栈溢出？

回答

相关问题