Question

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

#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;
}

Answer 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);
}
}

追问

强啊，我那个是学校数据结构上的书看的，不过看不太懂你代码，模板没怎么用过啊，能加点注释不？

Answer 2

快速排序是不稳定的，最差的时候时间度最长，递归的层数就是最大！有可能会引起栈溢出！

归并排序是稳定的排序，最差和最好情况时间度是一样的！

对于快速排序，关键值一般是取第一个，可以试着取中间位置的值……情况会有改善，但还是存在不稳定性！

Answer 3

这样解决：
#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;
}
原因：
递归调用当计算符合条件时，是一层一层返回，并非直接返回到主函数

追问

你这个排序不正确，你调试下，数组10的都排不了

追答

排序算法我是直接照搬上面的，正确性我没验证，我要说的是递归算法程序框架设计问题，而不是算法的正确性