《内部排序算法效率比较平台的设计与实现》由会员分享,可在线阅读,更多相关《内部排序算法效率比较平台的设计与实现(17页珍藏版)》请在金锄头文库上搜索。
1、河北工业大学河北工业大学数据结构数据结构课程实验课程实验实实 验验 报报 告告题目:题目: 内部排序算法效率比较平台的设计与实现 专业:专业: 计算机科学与技术 班级:班级: 姓名:姓名: 学号:学号: 完成日期:完成日期: 一、试验内容一、试验内容各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。设计和实现内部排序算法效率比较平台,通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观的感受。二、试验目的二、试验目的掌握多种排序方法的基本思想,如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法,并能够用高级语言实现。三、三、源程序代码源程序代码
2、#include #include #include #define le 100 struct point char key11; ; /冒泡法void maopao(point c) point a,ble; int i,j,jh=0,bj=0,q; for(i=0;ii;j-) bj=bj+1;q=strcmp(bi.key,bj.key); if(q=1) a=bi; bi=bj; bj=a; jh=jh+3; ; ; ; cout0j=j-dk) cj+dk=cj;d1=d1+1; q=strcmp(a.key,cj-dk.key); cj+dk=a;d1=d1+1; ; ; ; v
3、oid shellsort(point c,int dlta,int t) int k,d2,i;d0=0;d1=0; point ble+1; for(k=0;k=0;i-) q=strcmp(bi.key,b2*i.key);*bj=*bj+1; if(q=-1) a=bi;bi=b2*i;b2*i=a;*jh=*jh+3; ; if(2*i+11;i-) diu(b,i,j,bl); ;cout“堆排序:“endl“完成的序列如下:“endl;for(i=0;ile;i+) coutbi.key“ “; ; coutendl“共进行比较“bj“次,进行交换“jh“次“endl“*“end
4、l; ; void main() int i,j,n=10,ans,an; char b=“abcdefghijklmnopqrstuvwxyz“; point ale; for(i=0;ile;i+) n=10; an=rand()*(n-1)/RAND_MAX+1; n=26; for(j=0;jan;j+) ans=rand()*(n-0)/RAND_MAX+0; ai.keyj=bans; ; ai.keyj=0; ; for(i=0;ile;i+) coutai.keyendl; ; zhijiecharu(a); maopao(a); xier(a); jiandanxuanze(
5、a); kuaisu(a); diup(a); ;四、四、流程图流程图开始产生100个随 机字符串直接插入 排序排序输出序列和交换次 数及比较次数起泡排序排序输出序列和交换次 数及比较次数希尔排序排序输出序列和交换次 数及比较次数简单选择 排序排序输出序列和交换次 数及比较次数快速排序排序输出序列和交换次 数及比较次数堆排序排序输出序列和交换次 数及比较次数结束五、调试过程五、调试过程要很好的理解各种算法就可以这样才可以编出程序来,要注意比较次数和交换次数的 计数问题。六、结果分析六、结果分析运行结果如下:ovpjxvtesnhacjdeldaajnopprlbpuuhwsyydmgwfvzz
6、pkghvjrahhprvsmftlytcptpojflnztiermbndydxshbzrdvpeevmenkhortsmjvnlcyxoijwilhhtoftvknxzbnfvqrvdtyhitvptgdabufdoacltrblfshgpnqnzyeiezlzqlbxhftkfqpmpqwvsojetogepspjmctqrudowpsbrziohewteicbqvokhmndtivwshydbunpbwricnfhxrcmjmnjrnpkasqmtmjuojyejdtypiqwwswadsqbeiijruupuxdqgdwbohofcvduxupjwfwfgzbcnlggddycbbi
7、xlyvnskganykggrylxapuodfjakcwbvrrurdrsuwscoybhzqxjsegxcxlcezuwflatkibgegdqxyfqrxlxrdqkyopngjaufkbfeqlplrkvpfykzexolqshkxsxkkxikottttfh直接插入排序:完成的序列如下:a be bfeqlp bgegdqxyf blfsh bnfvqr bpuu bwricnfhx bxhftkfqp bzrd cvd dmgwf eg ejdtyp ezuwflat fdoacltr fh fl g gddycbbixgdwb gepspjmct gpnq grylxa h hh
8、prvsmft htoftvknx hwsyy i iijruu j jauf jv jwilh jxvte k khmnd khortsm ki kxs kyopng kzexolqs l lcyxoi ldaajnopp lrkvpfy lytcp lyvn mpqwv mtmjuojy nndydxsh njrnpkas nz nztiermb o ohof pjwfwfg psbrziohe ptgdabupuodfjakc puxdq q q q qrudow qrxlxrdq r rcmjm rdrsu rlscoybh skganykg snhacjde sojeto swads
9、q t teicbqvo tiv tpoj tttt tv uxu vd vp vpeevmen vzzpkghv w w wbvrru wshydbunp wwxcxlc xjs xkkxiko yeiezlz yhi z zbcnl zq共进行比较 2528 次,进行交换 2616 次*起泡法:完成的序列如下:a be bfeqlp bgegdqxyf blfsh bnfvqr bpuu bwricnfhx bxhftkfqp bzrd cvd dmgwf eg ejdtyp ezuwflat fdoacltr fh fl g gddycbbixgdwb gepspjmct gpnq gr
10、ylxa h hhprvsmft htoftvknx hwsyy i iijruu j jauf jv jwilh jxvte k khmnd khortsm ki kxs kyopng kzexolqs l lcyxoi ldaajnopp lrkvpfy lytcp lyvn mpqwv mtmjuojy nndydxsh njrnpkas nz nztiermb o ohof pjwfwfg psbrziohe ptgdabupuodfjakc puxdq q q q qrudow qrxlxrdq r rcmjm rdrsu rlscoybh skganykg snhacjde soj
11、eto swadsq t teicbqvo tiv tpoj tttt tv uxu vd vp vpeevmen vzzpkghv w w wbvrru wshydbunp wwxcxlc xjs xkkxiko yeiezlz yhi z zbcnl zq共进行比较 4950 次,进行交换 2469 次*希尔排序:完成的序列如下:a be bfeqlp bgegdqxyf blfsh bnfvqr bpuu bwricnfhx bxhftkfqp bzrd cvd dmgwf eg ejdtyp ezuwflat fdoacltr fh fl g gddycbbixgdwb gepspjm
12、ct gpnq grylxa h hhprvsmft htoftvknx hwsyy i iijruu j jauf jv jwilh jxvte k khmnd khortsm ki kxs kyopng kzexolqs l lcyxoi ldaajnopp lrkvpfy lytcp lyvn mpqwv mtmjuojy nndydxsh njrnpkas nz nztiermb o ohof pjwfwfg psbrziohe ptgdabupuodfjakc puxdq q q q qrudow qrxlxrdq r rcmjm rdrsu rlscoybh skganykg sn
13、hacjde sojeto swadsq t teicbqvo tiv tpoj tttt tv uxu vd vp vpeevmen vzzpkghv w w wbvrru wshydbunp wwxcxlc xjs xkkxiko yeiezlz yhi z zbcnl zq共进行比较 838 次,进行交换 800 次*简单选择排序排序:完成的序列如下:a be bfeqlp bgegdqxyf blfsh bnfvqr bpuu bwricnfhx bxhftkfqp bzrd cvd dmgwf eg ejdtyp ezuwflat fdoacltr fh fl g gddycbbixgdwb gepspjmct gpnq g