同样是调用递归算法，快速排序文件过大时栈溢出，而归并排序则不会，怎么解决

#include<iostream>
#include<string>
#include<time.h>
#include<stdlib.h>
using namespace std;
const int MAX=1000000;
//快速排序，排序算法
int Partition(int *quickSort,int low,int high)
{
int key=quickSort[low];
for(;low<high;)
{
while(low<high && quickSort[high]>=key)
--high;
quickSort[low]=quickSort[high];
while(low<high && quickSort[low]<=key)
++low;
quickSort[high]=quickSort[low];
}
quickSort[low]=key;
return low;
}
//快速排序，小->大,递归算法
bool QuickSort(int *quickSort,int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(quickSort,low,high);
QuickSort(quickSort,low,pivotloc-1);
QuickSort(quickSort,pivotloc+1,high);
}
return true;
}//QuickSort
//归并排序，两个有序子文件合并
void Merge(int *mergeSort,int low,int middle,int high)
{//将两个有序的子文件mergeSort[low..middle]和mergeSort[middle+1..high]
//归并成一个有序的子文件mergeSort[low..high]
int add=0,i=low,j=middle+1;
int *p;//p是局部指针
if(!(p=(int *)malloc((high-low+2)*sizeof(int))))
{//动态申请p，申请失败程序结束
exit(0);
}
for(;i<=middle&&j<=high;add++)
{ //两子文件非空时取其小者输出到p[add]上
p[add]=(mergeSort[i]<=mergeSort[j])?mergeSort[i++]:mergeSort[j++];
}
while(i<=middle)
p[add++]=mergeSort[i++];//若第一个文件非空，则将其值赋给p
while(j<=high)
p[add++]=mergeSort[j++];//若第二个文件非空，则赋其值给p
p[add]='/0';
for(add=0,i=low;i<=high;i++)
{
mergeSort[i]=p[add++];
}
free(p);
}
//归并排序，小->大
bool MergeSort(int *mergeSort,int low,int high)
{//用分治法对R[low..high]进行二路归并排序
int mid;
if(low<high)
{//区间长度大于1
mid=(low+high)/2; //分解
MergeSort(mergeSort,low,mid); //递归地对R[low..mid]排序
MergeSort(mergeSort,mid+1,high); //递归地对R[mid+1..high]排序
Merge(mergeSort,low,mid,high); //组合，将两个有序区归并为一个有序区
}
return true;
}//MergeSort
//main函数
int main ()
{
int *quickSort=new int[MAX+1];
int i;
srand((int)time(0));
//快速排序
clock_t start=clock();
for(i=0;i<MAX;i++)
{
while((quickSort[i]=(int)rand()%100)<5){}
//cout<<quickSort[i]<<" ";
}
quickSort[MAX]='/0';
clock_t start2=clock();
if(QuickSort(quickSort,0,MAX-1))
cout<<"当元素个数为："<<MAX<<"时，快速排序所用时间为："<<(float)(clock()-start2)/1000<<"秒"<<endl;
//for(i=0;i<MAX;i++)
// cout<<quickSort[i]<<" ";
delete[]quickSort;
//归并排序
int *mergeSort=new int [MAX+1];
for(i=0;i<MAX;i++)
{
mergeSort[i]=(int)rand()%100;
}
mergeSort[MAX]='/0';
clock_t start3=clock();
if(MergeSort(mergeSort,0,MAX-1))
cout<<"当元素个数为："<<MAX<<"时，归并排序所用时间为："<<(float)(clock()-start3)/1000<<"秒"<<endl;
// for(i=0;i<MAX;i++)
// cout<<mergeSort[i]<<" ";
delete[]mergeSort;
getchar();
return 1;
}

这样解决：
#include<iostream>
#include<string>
#include<time.h>
#include<stdlib.h>
using namespace std;
const int MAX=1000000;
int flag=0;
//快速排序，排序算法
int Partition(int *quickSort,int low,int high)
{
int key=quickSort[low];
for(;low<high;)
{
while(low<high && quickSort[high]>=key)
--high;
quickSort[low]=quickSort[high];
while(low<high && quickSort[low]<=key)
++low;
quickSort[high]=quickSort[low];
}
quickSort[low]=key;
return low;
}
//快速排序，小->大,递归算法
bool QuickSort(int *quickSort,int low,int high)
{
if(flag==0)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(quickSort,low,high);
QuickSort(quickSort,low,pivotloc-1);
QuickSort(quickSort,pivotloc+1,high);
}
}
flag = 1;
return true;
}//QuickSort
//归并排序，两个有序子文件合并
void Merge(int *mergeSort,int low,int middle,int high)
{//将两个有序的子文件mergeSort[low..middle]和mergeSort[middle+1..high]
//归并成一个有序的子文件mergeSort[low..high]
int add=0,i=low,j=middle+1;
int *p;//p是局部指针
if(!(p=(int *)malloc((high-low+2)*sizeof(int))))
{//动态申请p，申请失败程序结束
exit(0);
}
for(;i<=middle&&j<=high;add++)
{ //两子文件非空时取其小者输出到p[add]上
p[add]=(mergeSort[i]<=mergeSort[j])?mergeSort[i++]:mergeSort[j++];
}
while(i<=middle)
p[add++]=mergeSort[i++];//若第一个文件非空，则将其值赋给p
while(j<=high)
p[add++]=mergeSort[j++];//若第二个文件非空，则赋其值给p
p[add]='/0';
for(add=0,i=low;i<=high;i++)
{
mergeSort[i]=p[add++];
}
free(p);
}
//归并排序，小->大
bool MergeSort(int *mergeSort,int low,int high)
{//用分治法对R[low..high]进行二路归并排序
int mid;
if(low<high)
{//区间长度大于1
mid=(low+high)/2; //分解
MergeSort(mergeSort,low,mid); //递归地对R[low..mid]排序
MergeSort(mergeSort,mid+1,high); //递归地对R[mid+1..high]排序
Merge(mergeSort,low,mid,high); //组合，将两个有序区归并为一个有序区
}
return true;
}//MergeSort
//main函数
int main ()
{
int *quickSort=new int[MAX+1];
int i;
srand((int)time(0));
//快速排序
clock_t start=clock();
for(i=0;i<MAX;i++)
{
while((quickSort[i]=(int)rand()%100)<5){}
//cout<<quickSort[i]<<" ";
}
quickSort[MAX]='/0';
clock_t start2=clock();
if(QuickSort(quickSort,0,MAX-1))
cout<<"当元素个数为："<<MAX<<"时，快速排序所用时间为："<<(float)(clock()-start2)/1000<<"秒"<<endl;
//for(i=0;i<MAX;i++)
// cout<<quickSort[i]<<" ";
delete[]quickSort;
//归并排序
int *mergeSort=new int [MAX+1];
for(i=0;i<MAX;i++)
{
mergeSort[i]=(int)rand()%100;
}
mergeSort[MAX]='/0';
clock_t start3=clock();
if(MergeSort(mergeSort,0,MAX-1))
cout<<"当元素个数为："<<MAX<<"时，归并排序所用时间为："<<(float)(clock()-start3)/1000<<"秒"<<endl;
// for(i=0;i<MAX;i++)
// cout<<mergeSort[i]<<" ";
delete[]mergeSort;
getchar();
return 1;
}
原因：
递归调用当计算符合条件时，是一层一层返回，并非直接返回到主函数

不知道你在哪里看到的快速排序，虽然写得这么纠结，但是结果还是对的。快速排序跟归并排序的最大区别是归并排序需要额外的空间，这个空间你是在堆里分配的，而快速递归不需要申请一个O(n)空间是因为通过函数栈保存了一些中间数据，正常来说当你元素很多时比如大于1M，函数栈肯定会溢出的，因为函数栈一般默认大小就是1M，函数栈大小是可以设置的，怎么设置函数栈大小你可以查百度。这些或许你都知道，不过你的递归算法也有点问题，因为你中间元素key就取了第一个元素，这会使得出现很多的递归浪费大量的栈空间，比如元素本来就有序的以你的算法时间复杂度为T(n) = T(n-1) + n，这个时间复杂度是O（n*n），递归次数为n，正常情况递归次数应该是log（n）次的，你递归了时间不说栈空间就需要很大，所以这也可能是你栈溢出的一个可能。快速排序的中间元素key不能去第一个元素就行了，即使随机取一个都比你取第一个好多了。这里有我之前写的一个快速排序 struct my_traits<T*> { typedef T value_type; } template<class BidirectIterator> void IterSwap(BidirectIterator i,BidirectIterator j) { if(*i == *j) return; typename my_traits<BidirectIterator>::value_type temp = *i; *i = *j; *j = temp; } template<class T> void InsertSort(T *first,T *last) { for(T *i = first + 1;i < last;++i) { T value = *i; T *j = 0; for(j = i;j - 1 >= first&&*(j - 1) > value;--j) *j = *(j - 1); *j = value; } } template<class T> T Median3(T*first,T*last) { T * middle = first + (last - first) / 2; last--; if(*first > *middle) IterSwap(first,middle); if(*first > *last) return *first; if(*middle < *last) return *middle; return *last; } template<class T> T* Partition(T *first,T *last,T pivot) { while(true) { while(*first < pivot) ++first; --last; while(*last > pivot) --last; if(first > last) return first; IterSwap(first,last); ++first; } } template<class T> void QuikSort(T *first,T *last) { if(last - first >= 4) { T *cut = Partition(first,last,Median3(first,last)); QuikSort(first,cut); QuikSort(cut,last); } else { InsertSort(first,last); } }

这样解决： #include #include #include #include using namespace std; const int MAX=1000000; int flag=0; //快速排序，排序算法 int Partition(int *quickSort,int low,int high) { int key=quickSort[low]; for(;low=key) --high; quickSort[low]=quickSort[high]; while(low大,递归算法 bool QuickSort(int *quickSort,int low,int high) { if(flag==0) { int pivotloc; if(low

• 3楼网友：野慌
• 2021-03-12 12:27

快速排序是不稳定的，最差的时候时间度最长，递归的层数就是最大！有可能会引起栈溢出！ 归并排序是稳定的排序，最差和最好情况时间度是一样的！ 对于快速排序，关键值一般是取第一个，可以试着取中间位置的值……情况会有改善，但还是存在不稳定性！

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

大家都在看

为什么vagaa下下来安装上但不能运行

盛和堂医药连锁玉泉店地址在什么地方，想过去

愚这个词是褒义还是贬义

新奇骏火花塞是白金还是铱金的

中华小当家真假七星刀对决的是哪一集？

捷佳咖啡·生活馆地址在哪，我要去那里办事

凉山州北控水环境投资有限公司怎么样？

牧尘炼的是什么灵兽，她的老婆是谁？有多少个

从事建筑设计的，大学专业不是工科的。现在想

甜蜜村儿童乐园在哪里啊，我有事要去这个地方

求带英语和国语字幕的海底总动员和汽车总动员

火柴人联盟单挑之王游戏挑战中分为精英副本和

368路青岛市未来公交

如何做淘宝客推广

小区的地下室可以住人吗？

推荐资讯

第9题④怎么看

东平县二建总公司地址在什么地方，想过去办事

为什么有些人就是那么衰？

天津市河东区十三经路加油站怎么去啊，有知道

为什么同样用iphone4上QQ人家显示IPHONE QQ在

弹棉花需要办理营业执照吗？

斯柯达晶锐1.4自动挡上好牌多少钱

日本修士留学生学历学位认证？

四川省交通运输厅高速公路交通执法第六支队地

穿什么颜色是最高级的神仙

东湖龙源宾馆怎么去啊，有知道地址的么

怎么才能哄女孩子不生气呢？

正方形一边上任一点到这个正方形两条对角线的

阴历怎么看 ？