課程設計報告內排序算法比較

1、數(shù)據(jù)結構課程設計報告提交日期： 8月20日 成績： 指導老師：實驗題目： 內排序算法比較問題解析（對問題的分析、理解和解題方法）：1. 偽隨機數(shù)的產(chǎn)生是由 time. h 頭文件,以rand(time(0)為隨機種子的函數(shù)rand()產(chǎn)生，可以保持數(shù)據(jù)的無序性。2. 生成三種文件，分別保存正序.逆序.和隨機產(chǎn)生的數(shù)據(jù)，并在程序執(zhí)行過程中可選擇用某一文件中的數(shù)據(jù)。3. 用類涵蓋六種排序算法的內部操作，并定義數(shù)組元素類。4. 輸入以文件的方式來進行，必須保證對六種排序算法的輸入數(shù)據(jù)是一樣且連續(xù)的。5. 對于比較次數(shù)的統(tǒng)計加在比較判斷的前邊，在判斷失敗時也能統(tǒng)計到比較次數(shù)。6. 對于存在遞歸的快速排

2、序和存在子函數(shù)的堆排序的比較次數(shù).移動次數(shù)統(tǒng)計采用以引用做函數(shù)參數(shù)。數(shù)據(jù)結構選擇：選用動態(tài)數(shù)組為內部基本運算結構，外部數(shù)據(jù)選用文件。算法設計：構建動態(tài)數(shù)組元素類，六種排序操作.輸出操作為該類的函數(shù)，輸入操作包含在構造函數(shù)中。需求分析：外部數(shù)據(jù)只可以手動輸入隨機數(shù)的個數(shù)。程序運行中可選擇采用多種文件用各種算法測試多次。程序主線：產(chǎn)生正序文件f1.txt，倒序文件f2.txt，并生成三個隨機文件f3.txt f4.txt f5.txt。選擇將某一文件導入程序，進行排序，并測試各種算法的移動和比較次數(shù)。最后對結果進行分析。任務分工、進度計劃：周一：六種排序算法嵌入各主程序，并進行初步測算。周二：主要

3、解決程序文件輸入，輸出問題和各函數(shù)的接口問題。周三：對程序進行調整，解決部分錯誤輸出。用戶手冊： 用戶需要選擇是否生成新的文件，還需要外部輸入待排序數(shù)組元素個數(shù)即可，程序運行中用戶可選擇用某一文件進行排序。測試結果：請輸入排序元素個數(shù):10000請輸入讀入何種待排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)0bubble:比較次數(shù)=9999 移動次數(shù)：=0insertsort:比較次數(shù)=9999 移動次數(shù)：=19998ssort:比較次數(shù)=49995000 移動次數(shù)：=29997qsort:比較次數(shù)=19998 移動次數(shù)：=39996shellsort:比較次

4、數(shù)=120009 移動次數(shù)：=240018heapsort:比較次數(shù)=264502 移動次數(shù)：=394251是否繼續(xù)測試:(按任意鍵繼續(xù)，按0退出:)1請輸入排序元素個數(shù):10000請輸入讀入何種待排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)1bubble:比較次數(shù)=49995000 移動次數(shù)：=149985000insertsort:比較次數(shù)=9999 移動次數(shù)：=19998ssort:比較次數(shù)=49995000 移動次數(shù)：=29997qsort:比較次數(shù)=19998 移動次數(shù)：=39996shellsort:比較次數(shù)=120009 移動次數(shù)：=24001

5、8heapsort:比較次數(shù)=264502 移動次數(shù)：=394251是否繼續(xù)測試:(按任意鍵繼續(xù)，按0退出:)1請輸入排序元素個數(shù):12000請輸入讀入何種待排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)2bubble:比較次數(shù)=71963151 移動次數(shù)：=109210041insertsort:比較次數(shù)=11999 移動次數(shù)：=23998ssort:比較次數(shù)=71994000 移動次數(shù)：=35997qsort:比較次數(shù)=19742 移動次數(shù)：=38153shellsort:比較次數(shù)=144012 移動次數(shù)：=288024heapsort:比較次數(shù)=3240

6、68 移動次數(shù)：=482526是否繼續(xù)測試:(按任意鍵繼續(xù)，按0退出:)1請輸入排序元素個數(shù):13000請輸入讀入何種待排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)3bubble:比較次數(shù)=84487519 移動次數(shù)：=126842301insertsort:比較次數(shù)=12999 移動次數(shù)：=25998ssort:比較次數(shù)=84493500 移動次數(shù)：=38997qsort:比較次數(shù)=21614 移動次數(shù)：=41570shellsort:比較次數(shù)=156009 移動次數(shù)：=312018heapsort:比較次數(shù)=353720 移動次數(shù)：=526605是否繼續(xù)

7、測試:(按任意鍵繼續(xù)，按0退出:)1請輸入排序元素個數(shù):14000請輸入讀入何種待排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)4bubble:比較次數(shù)=97891310 移動次數(shù)：=146827053insertsort:比較次數(shù)=13999 移動次數(shù)：=27998ssort:比較次數(shù)=97993000 移動次數(shù)：=41997qsort:比較次數(shù)=23354 移動次數(shù)：=44780shellsort:比較次數(shù)=168011 移動次數(shù)：=336022heapsort:比較次數(shù)=383566 移動次數(shù)：=571275是否繼續(xù)測試:(按任意鍵繼續(xù)，按0退出:)總結

8、（對所做程序進行分析、評價運行結果、總結遇到的問題及解決辦法）：總結：能輸出各種算法對同一數(shù)組的比較.交換次數(shù)，能較直觀的比較各種算法在不同情況下的優(yōu)劣。遇到如下問題：問題1：快速排序的遞歸中和堆排序的子函數(shù)中比較次數(shù)和移動次數(shù)無法同時返回解決辦法:引用比較次數(shù)compare和移動次數(shù)move作為函數(shù)的參數(shù)。問題2：在數(shù)組很大10000，正序或逆序時，快速排序堆棧溢出解決辦法：在編譯器中修改了堆棧上限。程序清單：#include#include#includeusing namespace std;class listspublic:int n;void savefile();lists();

9、int getlist(int n)return listn;void output();void bubble();void insertsort();void ssort();void qqsort(int m,int n,int &,int &);void qsort();void shellsort();void restore(int *tree,const int root,const int n,int &,int &);void heapsort();private:int *list;lists:lists() int s0; savefile(); cout請輸入讀入何種待

10、排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)s0; list=new intn; switch(s0) case 0:ifstream infile(f1.txt,ios:in); for(int i=0;ilisti; infile.close();break; case 1:ifstream infile(f2.txt,ios:in); for(int i=0;ilisti; infile.close();break; case 2:ifstream infile(f3.txt,ios:in); for(int i=0;ilisti; infile.cl

11、ose();break; case 3:ifstream infile(f4.txt,ios:in); for(int i=0;ilisti; infile.close();break; case 4:ifstream infile(f5.txt,ios:in); for(int i=0;ilisti; infile.close();break; void lists:output()for(int i=0;in;i+)coutlistiendl;/冒泡排序void lists:bubble()int bound,j,t;int e;int compare=0,move=0;bound=n-1

12、;while(bound)t=0;for(j=0;jlistj+1)move+=3;e=listj;listj=listj+1;listj+1=e;t=j;bound=t;coutbubble:比較次數(shù)=compare 移動次數(shù)：=moveendl;/直接插入排序void lists:insertsort()int e,i;int compare=0,move=0;/list-1=0;for(int j=1;jn;j+)e=listj;move+;i=j-1;compare+;while(elisti)listi+1=listi;move+;i-;listi+1=e;move+;coutins

13、ertsort:比較次數(shù)=compare 移動次數(shù)：=move=1;j-)t=0;for(int i=1;i=j;i+)compare+;if(listtlisti)t=i;e=listt;listt=listj;listj=e;move+=3;coutssort:比較次數(shù)=compare 移動次數(shù)：=moveendl;/快速排序void lists:qqsort(int m,int n,int &a,int &b)int i,j,k,temp;if(mn)i=m;j=n+1;k=listm;b+;while(ij)i+;a+;while(listik)j-;if(ij)temp=listi;

14、listi=listj;listj=temp;b+=3;temp=listm;listm=listj;listj=temp;b+=3;qqsort(m,j-1,a,b);qqsort(j+1,n,a,b);/快速排序void lists:qsort()int compare=0,move=0;qqsort(0,n-1,compare,move);coutqsort:比較次數(shù)=compare 移動次數(shù)：=move=1)gap=gap/2;for(i=0;igap;i+)int e;int t;for(int j=i+gap;jn;j=j+gap)e=listj;t=j-gap;move+;com

15、pare+;while(elistt)listt+gap=listt;t=t-gap;move+;if(t=i)break;listt+gap=e;move+;coutshellsort:比較次數(shù)=compare 移動次數(shù)：=moveendl;/重建堆void lists:restore(int *tree,const int root,const int n,int &a,int &b)int m,e;int j=root;while(j=n/2-1)a+;if(2*jn-1)&(tree2*jtree2*j+1)m=2*j+1;else m=2*j;a+;if(treej=0;i-)res

16、tore(list,i,n,compare,move);for(i=n-1;i0;i-)e=listi;listi=list0;list0=e;restore(list,0,i,compare,move);coutheapsort:比較次數(shù)=compare 移動次數(shù)：=moveendl;void lists:savefile() int i; srand(time(0); cout請輸入排序元素個數(shù):n; list=new intn; ofstream outfile1(f1.txt,ios:out); for(i=0;in;i+)listi=i+1;outfile1listiendl; ou

17、tfile1.close(); ofstream outfile2(f2.txt,ios:out); for(i=0;in;i+)listi=n-i;outfile2listiendl; outfile2.close(); ofstream outfile3(f3.txt,ios:out); for(i=0;in;i+)listi=rand()%10000+1;outfile3listiendl;outfile3.close(); ofstream outfile4(f4.txt,ios:out); for(i=0;in;i+)listi=rand()%10000+1;outfile4listiendl;outfile4.close(); ofstream outfile5(f5.txt,ios:out); for(i=0;in;i+)listi=rand()%10000+1;outfile5listiendl;outfile5.close();#include#include排序.husing namespace std;int s