修改后的測試結果：(可是修改之后隨機數排序時間的差距還是很大？請指點)
修改后的程序下載：
/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
魷魚 閱讀(3485)
評論(6) 編輯 收藏 引用