北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-排序

1、北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)四 排序?qū)W生姓名： 班 級： 班內(nèi)序號： 學(xué) 號： 日 期： 2014年1月4日1 實(shí)驗(yàn)?zāi)康膶W(xué)習(xí)、實(shí)現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。2 實(shí)驗(yàn)內(nèi)容2.1 題目1使用簡單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動(dòng)）。 3、對于這三類數(shù)據(jù)，比

2、較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）4、對2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時(shí)間復(fù)雜度編寫測試main()函數(shù)測試線性表的正確性。3 程序分析3.1 存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)數(shù)組3.2 關(guān)鍵算法分析1. 插入排序：依次將待排序的序列中的每一個(gè)記錄插入到先前排序好的序列中，直到全部記錄排序完畢void Insertsort(int r,int n,int* compare,int* move)/插入排序 *compare=0;*move=0;int i;int j;for(i=1;i<n;i+)/一共要排序n-1次int x=ri;for(j=i-1

3、;x<rj&&j>=0;j-) (*compare)+;(*move)+;rj+1=rj;if(j>=0) (*compare)+;rj+1=x;2. 希爾排序：先將整個(gè)序列分割成若干個(gè)子列，分別在各個(gè)子列中運(yùn)用直接插入排序，待整個(gè)序列基本有序時(shí)，再對全體記錄進(jìn)行一次直接插入排序void ShellInsert(int r,int n,int* compare,int* move)/希爾排序 *compare=0;*move=0;int j;10 9 12 12 20 20 31for(int d=n/2;d>=1;d=d/2)/間距越來越小for(in

4、t i=d;i<=n-1;i+)/從ad往后逐個(gè)元素確定是否需要前移if(ri<ri-d)/某元素比同組中的前一位小，則需要前移 int x=ri;for(j=i-d;(j>=0)&&(x<rj);j=j-d)/完成所需的所有前移(*compare)+;(*move)+;rj+d=rj; if(j>=0)(*compare)+; rj+d=x;else (*compare)+;3. 冒泡排序：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序記錄為止void Bubblesort(int r,int n,int* compare,int* mo

5、ve)/交換（冒泡）排序*compare=0;*move=0;int x;for(int j=0;j<n-1;j+)/冒泡排序n-1次 for(int i=n-1;i>j;i-) if(ri<ri-1) (*compare)+; (*move)+=3; x=ri; ri=ri-1; ri-1=x; else (*compare)+; 4. 快速排序：首先選擇一個(gè)基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對兩部分重復(fù)上述過程，直至整個(gè)序列排序完成int Partion(int r,int first,int end,int* compare,int* m

6、ove)/快速排序中的軸定位int i=first;int j=end;int zhou=ri;/默認(rèn)第一個(gè)元素為軸while(i<j)while(i<j)&&(rj>=zhou) /查看右側(cè)元素與軸的大小關(guān)系(*compare)+;j-;if(i<j)(*compare)+;(*move)+; ri=rj;/發(fā)現(xiàn)軸右側(cè)的某數(shù)比軸值小，將其前置while(i<j)&&(ri<=zhou)/查看左側(cè)元素與軸的大小關(guān)系(*compare)+; i+;if(i<j)(*compare)+; (*move)+; rj=ri;/發(fā)

7、現(xiàn)軸左側(cè)的某數(shù)比軸值小，將其后置ri=zhou;/最后確定軸的位置return i;void Qsort(int r,int i,int j,int* compare,int* move)/快速排序if(i<j)int centre=Partion(r,i,j,compare,move);Qsort(r,i,centre-1,compare,move);Qsort(r,centre+1,j,compare,move);5. 選擇排序：從待排序的記錄序列中選擇關(guān)鍵碼最小的記錄并將它與序列中的第一個(gè)記錄交換位置；然后從不包括第一個(gè)位置上的記錄序列中選擇關(guān)鍵碼最小（或最大）的記錄并將它與序列中

8、的第二個(gè)記錄交換位置；如此重復(fù)，直到序列中只剩下一個(gè)記錄為止void Selectsort(int r,int n,int* compare,int* move)/選擇排序*compare=0;*move=0;for(int i=0;i<n-1;i+)/排序n-1次 int min=i; for(int j=i+1;j<n;j+)/通過此層循環(huán)，找到真正的第i個(gè)最小值 (*compare)+; if(rj<rmin) min=j;/記錄下當(dāng)前找到的最小值的位置 if(min!=i) (*move)+=3; int Min; Min=rmin; rmin=ri; ri=Min;

9、 4 程序運(yùn)行結(jié)果4.1主函數(shù)流程圖4.2程序運(yùn)行框圖5 實(shí)驗(yàn)心得1.調(diào)試時(shí)出現(xiàn)的問題及解決的方法 在初期構(gòu)思代碼的時(shí)候，首先構(gòu)造了各種算法的基本實(shí)現(xiàn)代碼，封裝成類，已經(jīng)能夠?qū)崿F(xiàn)七種排序的基本功能，并且測試無誤。之后考慮如何能簡化代碼以實(shí)現(xiàn)多達(dá)七種排序算法的簡單調(diào)用、亂序和順序以及逆序數(shù)據(jù)的分別排序和性能指標(biāo)統(tǒng)計(jì)（算法移動(dòng)次數(shù)和比較次數(shù)的精確統(tǒng)計(jì)）。2.心得體會 程序的優(yōu)化是一個(gè)艱辛的過程，如果只是實(shí)現(xiàn)一般的功能，將變得容易很多，當(dāng)加上優(yōu)化，不論是效率還是結(jié)構(gòu)優(yōu)化，都需要精心設(shè)計(jì)。3. 改進(jìn)本程序代碼設(shè)計(jì)時(shí)運(yùn)用了遞歸的調(diào)用方式，效率還可以通過將其轉(zhuǎn)換為棧模擬的方式得以提高。另外還可以進(jìn)一步考慮

10、算法時(shí)間的精確統(tǒng)計(jì)，以便從時(shí)間角度比較這幾種排序算法的優(yōu)劣。完整源代碼#include<iostream>using namespace std;void Insertsort(int r,int n,int* compare,int* move);void ShellInsert(int r,int n,int* compare,int* move);void Bubblesort(int r,int n,int* compare,int* move);int Partion(int r,int first,int end,int* compare,int* move);void

11、 Qsort(int r,int i,int j,int* compare,int* move);void Selectsort(int r,int n,int* compare,int* move);void Insertsort(int r,int n,int* compare,int* move)/插入排序 *compare=0;*move=0;int i;int j;for(i=1;i<n;i+)/一共要排序n-1次int x=ri;for(j=i-1;x<rj&&j>=0;j-) (*compare)+;(*move)+;rj+1=rj;if(j&g

12、t;=0) (*compare)+;rj+1=x;void ShellInsert(int r,int n,int* compare,int* move)/希爾排序 *compare=0;*move=0;int j;for(int d=n/2;d>=1;d=d/2)/間距越來越小for(int i=d;i<=n-1;i+)/從ad往后逐個(gè)元素確定是否需要前移if(ri<ri-d)/某元素比同組中的前一位小，則需要前移 int x=ri;for(j=i-d;(j>=0)&&(x<rj);j=j-d)/完成所需的所有前移(*compare)+;(*mo

13、ve)+;rj+d=rj; if(j>=0)(*compare)+; rj+d=x;else (*compare)+;void Bubblesort(int r,int n,int* compare,int* move)/交換（冒泡）排序*compare=0;*move=0;int x;for(int j=0;j<n-1;j+)/冒泡排序n-1次 for(int i=n-1;i>j;i-) if(ri<ri-1) (*compare)+; (*move)+=3; x=ri; ri=ri-1; ri-1=x; else (*compare)+; int Partion(i

14、nt r,int first,int end,int* compare,int* move)/快速排序中的軸定位int i=first;int j=end;int zhou=ri;/默認(rèn)第一個(gè)元素為軸while(i<j)while(i<j)&&(rj>=zhou) /查看右側(cè)元素與軸的大小關(guān)系(*compare)+;j-;if(i<j)(*compare)+;(*move)+; ri=rj;/發(fā)現(xiàn)軸右側(cè)的某數(shù)比軸值小，將其前置while(i<j)&&(ri<=zhou)/查看左側(cè)元素與軸的大小關(guān)系(*compare)+; i+

15、;if(i<j)(*compare)+; (*move)+; rj=ri;/發(fā)現(xiàn)軸左側(cè)的某數(shù)比軸值小，將其后置ri=zhou;/最后確定軸的位置return i;void Qsort(int r,int i,int j,int* compare,int* move)/快速排序if(i<j)int centre=Partion(r,i,j,compare,move);Qsort(r,i,centre-1,compare,move);Qsort(r,centre+1,j,compare,move);void Selectsort(int r,int n,int* compare,int

16、* move)/選擇排序*compare=0;*move=0;for(int i=0;i<n-1;i+)/排序n-1次 int min=i; for(int j=i+1;j<n;j+)/通過此層循環(huán)，找到真正的第i個(gè)最小值 (*compare)+; if(rj<rmin) min=j;/記錄下當(dāng)前找到的最小值的位置 if(min!=i) (*move)+=3; int Min; Min=rmin; rmin=ri; ri=Min; void main()int i;int compare=0;int move=0;cout<<"請您先輸入一個(gè)正序數(shù)組哦&

17、quot;<<endl;int n;cout<<"請輸入數(shù)組中含有的元素?cái)?shù)量："cin>>n;int *r=new intn;cout<<"請輸入數(shù)組中的元素："for(i=0;i<n;i+) cin>>ri;int *a=new intn;for(i=0;i<n;i+) ai=ri;Insertsort(a,n,&compare,&move);cout<<"n插入排序結(jié)果為："for(i=0;i<n;i+) cout<&l

18、t;ai<<' 'cout<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;int *b=new intn;for(i=0;i<n;i+) bi=ri;ShellInsert(b,n,&compare,&move);cout<<"希爾排序結(jié)果為："for(i=0;i<n;i+) cout<<bi<<

19、9; 'cout<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;int *c=new intn;for(i=0;i<n;i+) ci=ri;Bubblesort(c,n,&compare,&move);cout<<"交換排序結(jié)果為："for(i=0;i<n;i+) cout<<ci<<' 'cout<

20、<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;compare=0;move=0;int *d=new intn;for(i=0;i<n;i+) di=ri;Qsort(d,0,n-1,&compare,&move);cout<<"快速排序結(jié)果為："for(i=0;i<n;i+) cout<<di<<' 'cout<

21、<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;int *e=new intn;for(i=0;i<n;i+) ei=ri;Selectsort(e,n,&compare,&move);cout<<"選擇排序結(jié)果為："for(i=0;i<n;i+) cout<<ei<<' 'cout<<"n比較次數(shù)為

22、"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;cout<<"再輸入一個(gè)逆序數(shù)組"<<endl;cout<<"請輸入數(shù)組中含有的元素?cái)?shù)量："cin>>n;cout<<"請輸入數(shù)組中的元素："for(i=0;i<n;i+) cin>>ri;for(i=0;i<n;i+) ai=ri;Insertsort(a,n,

23、&compare,&move);cout<<"n插入排序結(jié)果為："for(i=0;i<n;i+) cout<<ai<<' 'cout<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;for(i=0;i<n;i+) bi=ri;ShellInsert(b,n,&compare,&move);cout&l

24、t;<"希爾排序結(jié)果為："for(i=0;i<n;i+) cout<<bi<<' 'cout<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;for(i=0;i<n;i+) ci=ri;Bubblesort(c,n,&compare,&move);cout<<"交換排序結(jié)果為："for(i=

25、0;i<n;i+) cout<<ci<<' 'cout<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;compare=0;move=0;for(i=0;i<n;i+) di=ri;Qsort(d,0,n-1,&compare,&move);cout<<"快速排序結(jié)果為："for(i=0;i<n;i+) cou

26、t<<di<<' 'cout<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;for(i=0;i<n;i+) ei=ri;Selectsort(e,n,&compare,&move);cout<<"選擇排序結(jié)果為："for(i=0;i<n;i+) cout<<ei<<' 'co

27、ut<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;cout<<"最后輸入一個(gè)亂序數(shù)組"<<endl;cout<<"請輸入數(shù)組中含有的元素?cái)?shù)量："cin>>n;cout<<"請輸入數(shù)組中的元素："for(i=0;i<n;i+) cin>>ri;for(i=0;i<n;i+

28、) ai=ri;Insertsort(a,n,&compare,&move);cout<<"n插入排序結(jié)果為："for(i=0;i<n;i+) cout<<ai<<' 'cout<<"n比較次數(shù)為"<<compare;cout<<"n移動(dòng)次數(shù)為"<<move<<'n'<<endl;for(i=0;i<n;i+) bi=ri;ShellInsert(b,n,&compare,&move);cout<<"希爾排序結(jié)果為："for(i=0;i<n;i+) cout<<bi<<' 'cout<<