我对堆栈溢出没有太多的经验,我认为它们是由超过某个递归深度的递归函数引起的,为什么它们会在合并排序的这种迭代实现中在这里出现!
#include<iostream>
#include <stdlib.h>
#define SIZE 3000000
int L[2500002];
int R[2500002];
using namespace std;
int min(int a, int b) {
return !(b<a) ? a : b;
}
void Merge(int data[], int p, int q, int r)
{
if (q >= SIZE)q = (r + p) / 2;
int sizeL = q - p + 2;
int sizeR = r - q + 1;
for (int i = 0; i < sizeL - 1; i++)
L[i] = data[i + p];
for (int i = 0; i < sizeR - 1; i++)
R[i] = data[i + q + 1];
int max;
if (L[sizeL - 2]>R[sizeR - 2])
max = L[sizeL - 2] + 1;
else
max = R[sizeR - 2] + 1;
L[sizeL - 1] = R[sizeR - 1] = max;
int indexL = 0, indexR = 0;
for (int i = p; i <= r; i++){
if (L[indexL] <= R[indexR]){
data[i] = L[indexL];
indexL++;
}
else{
data[i] = R[indexR];
indexR++;
}
}
}
void MergeSort(int data[], int p, int r)
{
for (int i = 1; i< SIZE; i *= 2)
for (int j = 0; j < SIZE; j += 2 * i)
Merge(data, j, j + i - 1, min((j + 2 * i - 1), SIZE - 1));
}
/*****************************************************************************/
bool IsSorted(int data[], int size)
{
int i;
for (i = 0; i<(size - 1); i++)
{
if (data[i] > data[i + 1])
return false;
}
return true;
}
int main()
{
int data[SIZE];
for (int i = 0; i < SIZE; i++)
data[i] = rand();
MergeSort(data,0,SIZE-1);
if(IsSorted(data, SIZE))
cout << "Sorted correctly";
else
cout << "incorrect sorting";
getchar();
return 0;
}
最佳答案
int main()
{
int data[SIZE];
...
在堆栈上声明数组。堆栈大小有限制。它随操作系统和配置的不同而不同,但是很容易小于您要求的大小(假设32位整数)小于12 MB。尝试在堆上分配数组,而不是使用
std::vector
。编译器不可能就此问题警告您,因为堆栈大小是由OS在加载程序时设置的。您可以将操作系统重新配置为默认使用一个很小的堆栈,而以前运行过的程序将突然开始溢出。
如果您想了解有关操作系统如何检测堆栈溢出的更多信息,请查找虚拟内存,MMU和保护页面。