修改后的测试结果：(可是修改之后随机数排序时间的差距还是很大？请指点)
修改后的程序下载：
/Files/youyu/qSort.rar修改后的程序代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 50000 //定义排序数组的个数
#define N2 5000
int partition(int [],int,int);//快速排序分开数组的函数声明
void qSort(int [],int,int);//快速排序函数声明
void merge(int [],int,int,int);//归并排序数组合并函数声明
void mergesort(int [],int,int);//归并排序数组排序函数声明
//主函数
void main()
{
int i,a[N],a1[N],b[N2],b1[N2];//(已修改)增加了两个用来存储临时数据的数组
double t1,t2,t3,t4;
for(i=0;i<N;i++)
{
a[i]=rand()%N;//使用随机数作为参数
a1[i]=rand()%N;//(修改)*****************************
}
for(i=0;i<N2;i++)
{
b[i]=i;//使用已经排好序的一组数作为参数
b1[i]=i;
}
//快速排序N个随机数字所用的时间
t1=clock();
qSort(a,0,N-1);
t1=clock()-t1;
//归并排序N个随机数字所用的时间
t2=clock();
mergesort(a1,0,N-1);//(修改)*****************************
t2=clock()-t2;
//快速排序N2个已经排序的数字所用的时间
t3=clock();
qSort(b,0,N2-1);
t3=clock()-t3;
//归并排序N2个已经排序的数字所用的时间
t4=clock();
mergesort(b1,0,N2-1);//(修改)*****************************
t4=clock()-t4;
printf("\n快速排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t1);
printf("\n归并排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);
printf("\n快速排序%d个已经排序数字所用时间为:%f毫秒\n",N2,(double)t3);
printf("\n归并排序%d个已经排序数字所用时间为:%f毫秒\n\n",N2,(double)t4);
}
//快速排序
//快速排序分开数组函数的具体实现
int partition(int a[],int low,int high)
{
int pivotkey=a[low];
while(low<high)
{
while(low<high && a[high]>=pivotkey)
{
high--;
}
a[low]=a[high];
while(low<high && a[low]<=pivotkey)
{
low++;
}
a[high]=a[low];
}
a[low]=pivotkey;
return low;
}
//快速排序函数的具体实现
void qSort(int a[],int left,int right)
{
if(left<right)
{
int key=partition(a,left,right);
qSort(a,left,key-1);
qSort(a,key+1,right);
}
}
//归并排序
//归并排序合并数组函数的具体实现
void merge(int a[],int low,int middle,int high)
{
int h,i,j,k;
int b[N];
h=low;
i=low;
j=middle+1;
while(h<=middle&&j<=high)
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>middle)
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
else
{
for(k=h;k<=middle;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
}
//归并排序函数的具体实现
void mergesort(int a[],int low,int high)
{
int middle;
if(low<high)
{
middle=(low+high)/2;
mergesort(a,low,middle);
mergesort(a,middle+1,high);
merge(a,low,middle,high);
}
}posted on 2007-05-06 00:35
鱿鱼 阅读(3426)
评论(6) 编辑 收藏 引用