中国科技大学算法导论第一次实验报告Word文件下载.docx

中国科技大学算法导论第一次实验报告Word文件下载.docx

《中国科技大学算法导论第一次实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《中国科技大学算法导论第一次实验报告Word文件下载.docx（12页珍藏版）》请在冰点文库上搜索。

2、算法思想

累加k的值，计算出当k为不同值时算法运行的时间，来算出当k大约为什么值时运行的时间最短，并与传统的快速排序算法的运行时间进行比较。

3、实验结果

输入100个不同的整数值，选取不同的k的值，观察所用时间

4、实验分析

理论上看，k的值选取为20到25较好；

但是，从实际上来看，当k为50左右时间为39毫秒，最少，但不同的时刻运行后的时间都不相同，而且不同的输入时刻的运行时间也不相同，当数据较大时候，对k的值的选取有会有所不同，同时不同性能的机器对测试结果也不同，所以对于k值的选取没有固定的数值。

#include<

iostream>

sys/timeb.h>

usingnamespacestd;

#defineM40

voidswap（int*a,int*b）

{

inttem;

tem=*a;

*a=*b;

*b=tem;

}

intpartition（intv[],constintlow,constinthigh）

inti,pivotpos,pivot;

pivotpos=low;

pivot=v[low];

for（i=low+1;

i<

=high;

++i）

{

if（v[i]<

pivot）

pivotpos++;

if（pivotpos!

=i）swap（v[i],v[pivotpos]）;

}

v[low]=v[pivotpos];

v[pivotpos]=pivot;

//cout<

<

"

thepartitionfunctioniscalled\n"

;

returnpivotpos;

/*

voidQuickSort（inta[],constintlow,constinthigh）

intitem;

if（low<

high）

item=partition（a,low,high）;

QuickSort（a,low,item-1）;

QuickSort（a,item+1,high）;

*/

if（high-low<

=M）return;

//cout<

theQuickSortiscalled"

endl;

voidInsertSort（inta[],constintlow,constinthigh）

inti,j;

for（i=1;

high+1;

tem=a[i];

j=i-1;

while（j>

=0&

&

tem<

a[j]）

a[j+1]=a[j];

j--;

a[j+1]=tem;

theInsertSortiscalled"

voidHybridSort（inta[],constintlow,constinthigh）

QuickSort（a,low,high）;

InsertSort（a,low,high）;

cout<

theHybidSortiscalled"

intmain（）

inti,a[100];

//int*a=NULL;

longintt;

structtimebt1,t2;

/*cout<

pleaseinputthenumberoftheelement:

cin>

>

n;

a=（int*）malloc（n*sizeof（int））;

pleaseinputeveryelement:

*/

for（i=0;

i<

100;

i++）

a[i]=i+10;

//QuickSort（a,0,n-1）;

ftime（&

t1）;

HybridSort（a,0,99）;

aftersortedquickly,theresultis"

for（i=0;

cout<

a[i]<

"

if（i%10==0）cout<

t2）;

t=（t2.time-t1.time）*1000+（t2.millitm-t1.millitm）;

/*计算时间差*/

printf（"

k=%d用时%ld毫秒\n"

M,t）;

thememoryofarrayaisfree"

//free（a）;

\n"

return0;

----------THEEND,THEREISNOTXTFOLLOWING.------------