試驗十二排序技術(shù)試驗報告匯總

1、特殊線性表實驗十二 排序技術(shù)實驗一、 實驗目的 掌握各種排序算法的基本思想； 掌握各種排序算法的實現(xiàn)方法； 掌握各種排序算法的時間性能及其花費時間的計算。 掌握各種排序算法所適應的不同場合。二、 實驗內(nèi)容1、隨機函數(shù)產(chǎn)生 10000 個隨機數(shù)，用直接插入、希爾、冒泡、直接選擇等排序方法排序，并統(tǒng)計每 一種排序所花費的時間。2、隨機函數(shù)產(chǎn)生 30000 個隨機數(shù)，用快速、堆、歸并等排序方法排序，并統(tǒng)計每一種排序所花費的時 間。、設計與編碼#include #include #include using namespace std; void ShuChu(int r,int n) cout 輸出

2、： ;for(int i=0;in;i+) coutrit;coutendl;coutendl;void InsertSort(int r,int n) /int a=r0;for(int i=2;in;i+)r0=ri;for(int j=i-1;r0=1;d=d/2)插入排序希爾排序for(int i=d+1;i0 & r0rj;j=j-d)rj+d=rj;rj+d=r0;r0=a;void BubbleSort(int r,int n) / 冒泡排序int exchange=n-1;while(exchange!=0)int bound=exchange;exchange=0;for(i

3、nt j=1;jrj+1)int s=rj+1;rj+1=rj;rj=s;exchange=j;void SelectSort(int r,int n) / 選擇排序for(int i=0;in-1;i+)int index=i;for(int j=i+1;j=n-1;j+)if(rjrindex)index=j;if(index!=i)int a=rindex;rindex=ri;ri=a;ShuChu(r,n);次劃分算法int Partition(int r,int first,int end) /快速排序特殊線性表int i=first; int j=end;r0=ri;int p=r

4、i;while(ij)while(ij&ri=rj)j-;if(ij)int a=rj; rj=ri; ri=a;i+;while(ij&ri=rj)i+;if(ij)int b=rj; rj=ri; ri=b; j-; return i;void QuickSort(int r,int first,int end) / 快速排序算法 int a=r0;if(firstend)int pivot=Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end); r0=a;void Sift(int r,int

5、 k,int m) / 篩選法調(diào)整堆的算法int i=k;int j=2*i;while(j=m)if(jm&rj=rj)break;elseint a=rj;rj=ri;ri=a;i=j;j=2*i;void HeapSort(int r,int n) / 堆排序算法 for(int i=n/2;i=1;i-)Sift(r,i,n-1);for(i=2;in-1;i+)int a=rn-i+1;rn-i+1=r1;r1=a;Sift(r,1,i-1);次歸并算法void Merge(int r,int r1,int s,int m,int t) /int i=s;int j=m+1;int

6、k=s;while(i=m&j=t)if(ri=rj)r1k+=ri+;else r1k+=rj+;if(i=m)while(i=m)r1k+=ri+;else while(j=t)r1k+=rj+;void MergePass(int r,int r1,int n,int h)int i=1;int a=n-2*h+1;while (i=a)Merge(r,r1,i,i+h-1,i+2*h-1);i+=2*h; if(in-h+1)Merge(r,r1,i,i+h-1,n); else for(int k=i;k=n;k+)特殊線性表r1k=rk;歸并排序非遞歸算法void MergeSor

7、t(int r,int r1,int n) /int h=1;while (hn)MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;void menu()coutcout 排序技術(shù)實驗 endl;endl;cout1. 直接插入排序 endl;cout2. 希爾排序 endl;cout3. 冒泡排序 endl; cout4. 直接選擇排序 endl;cout5. 快速排序 endl;cout6. 堆排序 endl;cout7. 歸并排序 endl; cout8. 退出 endl;int main()clock_t start,end;men

8、u();int flag=1; while(flag)coutint i;endl;couti;switch(i)case 1:int srand(30001);int a30001;int n;coutn;a0=0;秒endl;秒endl;秒endl;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout 直接插入排序結(jié)果： endl;start=clock();InsertSort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout 排序所用時間為 :count b

9、reak;case 2:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout 希爾排序結(jié)果： endl;start=clock();ShellSort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout 排序所用時間為 :count break; case 3:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;

10、i+)ai=rand();ShuChu(a,n);cout 冒泡排序結(jié)果： endl;start=clock();BubbleSort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout 排序所用時間為 :count特殊線性表break; case 4:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout 直接選擇排序結(jié)果： endl; start=clock();SelectS

11、ort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout 排序所用時間為 :count break; case 5:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout 快速排序結(jié)果： endl; start=clock();QuickSort(a,1,n-1);end=clock();ShuChu(a,n);double count=(double)(end-start)/1

12、000;cout 排序所用時間為 :count break;case 6:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout 堆排序結(jié)果： endl;:endl;秒endl;秒endl;start=clock();HeapSort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout 排序所用時間為 :count 秒 endl;break; case 7:int srand(30

13、001);int a30001;int n;int a130001;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout 歸并排序結(jié)果： endl;start=clock();MergeSort(a,a1,n-1);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout 排序所用時間為 :count 秒 endl;break; case 8:flag=0;break; default:cout 錯誤 !endl;break;return 0; 四、運行與調(diào)試a) 在調(diào)試程序的過程中遇到什么問題，是如何解決的？ 答：數(shù)據(jù)的下標經(jīng)常出錯，數(shù)組的第一個數(shù)應是 a0.b) 設計了哪些設計數(shù)據(jù)？測試結(jié)果是什么？答：程序設計了對隨機函數(shù)產(chǎn)生 10000 個隨機數(shù)進行直接插入、希爾、冒泡、直接選擇等排序方法排 序，并統(tǒng)計每一種排序所花費的時間；對隨機函數(shù)產(chǎn)生 30000 個隨機數(shù)進行快速、堆、歸