快速排序的比较
关于堆栈的问题，为什么在数据较多时，快速排序跟归并排序会有栈溢出的错误，而且快速排序在排列随机数的时候没有出现栈溢出的问题啊。。实在不懂。还有就是关于堆跟栈，栈到底是什么东西，是怎么分配的。每个函数一个栈吗？还是每个程序一个栈？栈的大小又是多少？我在main（）函数里定义的数组有一定的限制是因为栈吗？求大神指导。。。。。。代码如下
程序代码：#include "stdio.h"
#include "time.h"
#include "stdlib.h"
#define Length 10001//若要修改测试数据的量，直接修改length便可，方便维护程序（随机数据的数据量）
typedef struct test{
int data[Length];
double start,end;
int l;
}test;//为了方便函数调用，定义测试数据的结构体
test original[3],tr2,a;//original,tr2,a 分别为原始数据，归并排序中的临时数组，实际排序的数据
void Ins_sort()
{
a.start=clock();
int j,i;
for(i=2;i<a.l;++i)
{
if(a.data[i]<a.data[i-1])
{
a.data[0]=a.data[i];
a.data[i]=a.data[i-1];
for(j=i-2;a.data[0]<a.data[j];j--)
a.data[j+1]=a.data[j];
a.data[j+1]=a.data[0];
}
}
a.end=clock();
printf("直接插入排序法耗时为：%lf\n",(a.end-a.start)/CLOCKS_PER_SEC);
}//直接插入排序法
//算法分析：直接插入排序法与数据是否有序有很大的关系，如果数组是正序的话其复杂度就会提高到O(n),如果数组恰好是逆序的话其复杂度就会变为O(n^2)
//直插排序容易理解，但是效率低
void She_sort()
{
a.start=clock();
int i,j,dk1[10]={357,237,193,137,99,63,40,13,4,1},dk=dk1[0];
for(int m=0;m<10;m++)
{
dk=dk1[m];
for(i=dk+1;i<a.l;++i)
{
if(a.data[i]<a.data[i-dk])
{
a.data[0]=a.data[i];
a.data[i]=a.data[i-dk];
for(j=i-dk;0<j&&a.data[0]<a.data[j];j-=dk)
a.data[j+dk]=a.data[j];
a.data[j+dk]=a.data[0];
}
}
}
a.end=clock();
printf("希尔排序法耗时为：%lf\n",(a.end-a.start)/ CLOCKS_PER_SEC);
}//希尔排序法
//当增量为2^（t-k+1）时间复杂度为O(n^1.5)
//
void Sle_sort()
{
int i,j,temp;
a.start=clock();
for(i=1;i<=a.l-1;++i)
{
temp=i;
for(j=i;j<a.l;++j)
{
if(a.data[temp]>a.data[j])temp=j;
}
if(temp!=i)
{
a.data[0]=a.data[i];
a.data[i]=a.data[temp];
a.data[temp]=a.data[0];
}
}
a.end=clock();
printf("选择排序法耗时为：%lf\n",(a.end-a.start)/ CLOCKS_PER_SEC);
}//选择排序法
//时间复杂度为O(n^2)
//
void Bub_sort()
{
int i,j;
bool change;//记录当前的数组是否已经有序
a.start=clock();
for(i=a.l-1,change=true;i>=1&&change;--i)
{
change=false;
for(j=1;j<i;++j)
{
if(a.data[j]>a.data[j+1])
{
a.data[0]=a.data[j];
a.data[j]=a.data[j+1];
a.data[j+1]=a.data[0];
change=true;
}
}
}
a.end=clock();
printf("起泡排序法耗时为：%lf\n",(a.end-a.start)/ CLOCKS_PER_SEC);
}//起泡排序法
//优点点是过程简单。在数组是正序时，不需要移动数据，而当数组是逆序时，其复杂度变为O(n^2)
//
int Partition(test &l,int low,int high)
{
int pivotkey=l.data[low];
l.data[0]=l.data[low];
while(low<high)
{
while(low<high&&l.data[high]>=pivotkey)--high;
l.data[low]=l.data[high];
while(low<high&&l.data[low]<=pivotkey)++low;
l.data[high]=l.data[low];
}
l.data[low]=l.data[0];
return low;
}//快排的一次
void Q_sort(int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(a,low,high);
Q_sort(low,pivotloc-1);
Q_sort(pivotloc+1,high);
}
}//快排的递归函数部分
void Qui_sort()
{
a.start=clock();
Q_sort(1,a.l-1);
a.end=clock();
printf("快速排序法耗时为：%lf\n",(a.end-a.start)/ CLOCKS_PER_SEC);
}//快速排序法
//快速排序法在所有的同数量级（O(nlogn)）的排序方法中，其平均性能最好
//但当数组有序时，它将蜕化为起泡排序
void heapadjust(test &h,int s,int m)
{
int rc=h.data[s],j;
for(j=2*s;j<=m;j*=2)
{
if(j<m&&h.data[j]<h.data[j+1])j++;
if(rc>=h.data[j])break;
h.data[s]=h.data[j];s=j;
}
h.data[s]=rc;
}//堆的一次调整
void Hea_sort()
{
a.start=clock();
for(int i=a.l/2;i>0;--i)heapadjust(a,i,a.l-1);//生成堆
for(int i2=a.l-1;i2>0;--i2)
{
a.data[0]=a.data[1];
a.data[1]=a.data[i2];
a.data[i2]=a.data[0];
heapadjust(a,1,i2-1);
}
a.end=clock();
printf("堆排序法耗时为：%lf\n",(a.end-a.start)/ CLOCKS_PER_SEC);
}//堆排序法
//时间复杂度为O(nlogn)
//
void merge(test sr,test &tr,int i,int m,int n)
{
int j,k;
for(j=m+1,k=i;i<=m&&j<=n;++k)
{
if(sr.data[i]<tr.data[j])tr.data[k]=sr.data[i++];
else tr.data[k]=sr.data[j++];
}
while(i<=m)tr.data[k++]=sr.data[i++];//复制剩余的
while(j<=n)tr.data[k++]=sr.data[j++];//复制剩余的
}//归并为m+n
void M_sort(test sr,test &tr1,int s,int t)
{
int m;
if(s==t)tr1.data[s]=sr.data[s];
else
{
m=(s+t)/2;
M_sort(sr,tr2,s,m);
M_sort(sr,tr2,m+1,t);
merge(tr2,tr1,s,m,t);
}
}
void Mer_sort()
{
a.start=clock();
M_sort(a,a,1,a.l-1);
a.end=clock();
printf("归并排序法耗时为：%lf\n",(a.end-a.start)/ CLOCKS_PER_SEC);
}//归并排序法
//归并排序法的优点是稳定，但在一般情况下很少使用
//
void compare(int i)
{
int choice;
a=original[i];
Ins_sort();
a=original[i];
She_sort();
a=original[i];
Sle_sort();
a=original[i];
Bub_sort();
a=original[i];
Qui_sort();
a=original[i];
Hea_sort();
a=original[i];
Mer_sort();
printf("1=输出排序结果 2=不输出(如果数据量过大，建议不要输出)\n");
scanf("%d",&choice);
if(1==choice)for(int i=0;i<a.l;i++)printf("%d ",a.data[i]);
printf("\n\n");
}//为了减少代码量，并依此比较随机，正序，逆序数组，定义了compare函数
int main()
{
printf("数据正在生成中，请稍后 ...\n");
srand((int)time(0));
for(int i=1;i<Length;i++){
original[0].data[i]=rand()%655365;
}
original[0].l=Length;
for(int i2=1;i<Length;i2++){
original[1].data[i2]=i2;
original[2].data[i2]=Length-i2;
}
printf("测试数据生成成功！\n\n");
original[1].l=Length;
original[2].l=Length;
for(int i3=0;i3<3;i3++)
{
switch(i3)
{
case 0:
printf("对于随机生成数据的比较如下:\n\n");
compare(i3);break;
case 1:
printf("对于正序数据比较如下：\n\n");
compare(i3);break;
case 2:
printf("对于逆序数据比较如下：\n\n");
compare(i3);break;
}
}
system("pause");
}
