試驗(yàn)十二排序技術(shù)試驗(yàn)報(bào)告匯總

1、特殊線性表實(shí)驗(yàn)十二 排序技術(shù)實(shí)驗(yàn)一、 實(shí)驗(yàn)?zāi)康?掌握各種排序算法的基本思想； 掌握各種排序算法的實(shí)現(xiàn)方法； 掌握各種排序算法的時(shí)間性能及其花費(fèi)時(shí)間的計(jì)算。 掌握各種排序算法所適應(yīng)的不同場合。二、 實(shí)驗(yàn)內(nèi)容1、隨機(jī)函數(shù)產(chǎn)生 10000 個(gè)隨機(jī)數(shù)，用直接插入、希爾、冒泡、直接選擇等排序方法排序，并統(tǒng)計(jì)每 一種排序所花費(fèi)的時(shí)間。2、隨機(jī)函數(shù)產(chǎn)生 30000 個(gè)隨機(jī)數(shù)，用快速、堆、歸并等排序方法排序，并統(tǒng)計(jì)每一種排序所花費(fèi)的時(shí) 間。、設(shè)計(jì)與編碼#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ù)實(shí)驗(yàn) 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 排序所用時(shí)間為 :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 排序所用時(shí)間為 :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 排序所用時(shí)間為 :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 排序所用時(shí)間為 :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 排序所用時(shí)間為 :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 排序所用時(shí)間為 :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 排序所用時(shí)間為 :count 秒 endl;break; case 8:flag=0;break; default:cout 錯(cuò)誤 !endl;break;return 0; 四、運(yùn)行與調(diào)試a) 在調(diào)試程序的過程中遇到什么問題，是如何解決的？ 答：數(shù)據(jù)的下標(biāo)經(jīng)常出錯(cuò)，數(shù)組的第一個(gè)數(shù)應(yīng)是 a0.b) 設(shè)計(jì)了哪些設(shè)計(jì)數(shù)據(jù)？測(cè)試結(jié)果是什么？答：程序設(shè)計(jì)了對(duì)隨機(jī)函數(shù)產(chǎn)生 10000 個(gè)隨機(jī)數(shù)進(jìn)行直接插入、希爾、冒泡、直接選擇等排序方法排 序，并統(tǒng)計(jì)每一種排序所花費(fèi)的時(shí)間；對(duì)隨機(jī)函數(shù)產(chǎn)生 30000 個(gè)隨機(jī)數(shù)進(jìn)行快速、堆、歸