數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——排序(共11頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1實(shí)驗(yàn)要求【實(shí)驗(yàn)?zāi)康摹?學(xué)習(xí)、實(shí)現(xiàn)、對(duì)比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況?！緦?shí)驗(yàn)內(nèi)容】使用簡(jiǎn)單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡(jiǎn)單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測(cè)試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動(dòng)）。 3、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）4、對(duì)2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的

2、時(shí)間復(fù)雜度編寫(xiě)測(cè)試main()函數(shù)測(cè)試線性表的正確性。2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)：數(shù)組r1r2 ri-1 ri ri+1 rn有序區(qū) 無(wú)序區(qū) 圖8-1 直接插入排序的基本思想圖解插入到合適位置2.2 關(guān)鍵算法分析/插入排序void InsertSort(int r, int n)int count1=0,count2=0;for (int i=2; i<n; i+) r0=ri; /設(shè)置哨兵for (int j=i-1; r0<rj; j-) /尋找插入位置rj+1=rj; /記錄后移rj+1=r0;count1+;count2+;for(int k=1;k<n

3、;k+)cout<<rk<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;/希爾排序void ShellSort(int r, int n)int i;int d;int j;int count1=0,count2=0; for (d=n/2; d>=1; d=d/2) /以增量為d進(jìn)行直接插入排序for (i=d+1; i<n; i+) r0=ri;

4、 /暫存被插入記錄for (j=i-d; j>0 && r0<rj; j=j-d)rj+d=rj; /記錄后移d個(gè)位置rj+d=r0;count1+;count2=count2+d;count1+;for(i=1;i<n;i+)cout<<ri<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;r1r2 ri-1 ri ri+1 r

5、n有序區(qū) 無(wú)序區(qū) 圖8-1 直接插入排序的基本思想圖解插入到合適位置/起泡排序void BubbleSort(int r, int n)int temp;int exchange;int bound;int count1=0,count2=0; exchange=n-1; /第一趟起泡排序的范圍是r1到rnwhile (exchange) /僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序bound=exchange; exchange=0; for(int j=0;j<bound;j+)/一趟起泡排序count1+;/接下來(lái)有一次比較if(rj>rj+1) temp=rj;/交換rj和rj

6、+1rj=rj+1;rj+1=temp;exchange=j;/記錄每一次發(fā)生記錄交換的位置count2=count2+3;/移動(dòng)了3次for(int i=1;i<n;i+)cout<<ri<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;/快速排序一次劃分int Partition(int r, int first, int end,int &co

7、unt1,int &count2)int i=first; /初始化 r1 ri-1 ri ri+1 rn 均ri 軸值 均ri 位于最終位置 圖8-6 快速排序的基本思想圖解int j=end;int temp; while (i<j) while (i<j && ri<= rj)j-; /右側(cè)掃描count1+;count1+;if (i<j) temp=ri; /將較小記錄交換到前面ri=rj;rj=temp;i+; count2=count2+3;while (i<j && ri<= rj) i+; /左側(cè)掃描

8、count1+;count1+;if (i<j)temp=rj;rj=ri;ri=temp; /將較大記錄交換到后面j-; count2=count2+3; return i; /i為軸值記錄的最終位置/快速排序void QuickSort(int r, int first, int end,int &count1,int &count2)if (first<end) /遞歸結(jié)束int pivot=Partition(r, first, end,count1,count2); /一次劃分QuickSort(r, first, pivot-1,count1,count

9、2);/遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序QuickSort(r, pivot+1, end,count1,count2); /遞歸地對(duì)右側(cè)子序列進(jìn)行快速排序r1 r2 ri-1 ri ri+1 rmin rn 有序區(qū) 無(wú)序區(qū) 已經(jīng)位于最終位置 rmin為無(wú)序區(qū)的最小記錄 圖8-9 簡(jiǎn)單選擇排序的基本思想圖解交換/簡(jiǎn)單選擇排序void SelectSort(int r , int n) int i;int j;int index;int temp;int count1=0,count2=0; for (i=0; i<n-1; i+) /對(duì)n個(gè)記錄進(jìn)行n-1趟簡(jiǎn)單選擇排序 index=i; f

10、or(j=i+1;j<n;j+)/在無(wú)序區(qū)中選取最小記錄count1+;/比較次數(shù)加一 if(rj<rindex)/如果該元素比現(xiàn)在第i個(gè)位置的元素小index=j;count1+;/在判斷不滿足循環(huán)條件j<n時(shí)，比較了一次 if(index!=i) temp=ri;/將無(wú)序區(qū)的最小記錄與第i個(gè)位置上的記錄交換 ri=rindex; rindex=temp;count2=count2+3;/移動(dòng)次數(shù)加3 for(i=1;i<n;i+)cout<<ri<<" "cout<<endl; cout<<&quo

11、t;比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;/篩選法調(diào)整堆void Sift(int r,int k,int m,int &count1,int &count2)/s，t分別為比較和移動(dòng)次數(shù)int i;int j;int temp;i=k; j=2*i+1; /置i為要篩的結(jié)點(diǎn)，j為i的左孩子while(j<=m)/篩選還沒(méi)有進(jìn)行到葉子if(j<m && rj<rj+1) j+;/比較i的左右孩子，j為較大者count1=co

12、unt1+2;/該語(yǔ)句之前和之后分別有一次比較if(ri>rj)break;/根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者else temp=ri; ri=rj; rj=temp;/將根結(jié)點(diǎn)與結(jié)點(diǎn)j交換 i=j; j=2*i+1;/下一個(gè)被篩結(jié)點(diǎn)位于原來(lái)結(jié)點(diǎn)j的位置count2=count2+3;/移動(dòng)次數(shù)加3/堆排序void HeapSort(int r,int n) int count1=0,count2=0;/計(jì)數(shù)器，計(jì)比較和移動(dòng)次數(shù)int i;int temp;for(i=n/2;i>=0;i-)/初始建堆，從最后一個(gè)非終端結(jié)點(diǎn)至根結(jié)點(diǎn)Sift(r,i,n,count1,count2)

13、 ; for(i=n-1; i>0; i-)/重復(fù)執(zhí)行移走堆頂及重建堆的操作temp=ri;/將堆頂元素與最后一個(gè)元素交換ri=r0;r0=temp;/完成一趟排序，輸出記錄的次序狀態(tài)Sift(r,0,i-1,count1,count2);/重建堆for(i=1;i<n;i+)cout<<ri<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;/一次歸并

14、void Merge(int r, int r1, int s, int m, int t)int i=s;int j=m+1;int k=s;while (i<=m && j<=t) if (ri<=rj) r1k+=ri+; /取ri和rj中較小者放入r1kelse r1k+=rj+; if (i<=m) while (i<=m) /若第一個(gè)子序列沒(méi)處理完，則進(jìn)行收尾處理 r1k+=ri+; else while (j<=t) /若第二個(gè)子序列沒(méi)處理完，則進(jìn)行收尾處理 r1k+=rj+; /一趟歸并void MergePass(int r

15、 , int r1 , int n, int h)int i=0;int k;while (i<=n-2*h) /待歸并記錄至少有兩個(gè)長(zhǎng)度為h的子序列Merge(r, r1, i, i+h-1, i+2*h-1); i+=2*h;if (i<n-h) Merge(r, r1, i, i+h-1, n); /待歸并序列中有一個(gè)長(zhǎng)度小于helse for (k=i; k<=n; k+) /待歸并序列中只剩一個(gè)子序列 r1k=rk;/歸并排序void MergeSort(int r , int r1 , int n ) int h=1;int i;while (h<n)Mer

16、gePass(r, r1, n-1, h); /歸并h=2*h;MergePass(r1, r, n-1, h);h=2*h;for(i=1;i<n;i+)cout<<ri<<" "cout<<endl;void Newarray(int a,int b,int c)cout<<"新隨機(jī)數(shù)組："c0=0;a0=0;b0=0;for(int s=1;s<11;s+)as=s;bs=20-s;cs=rand()%50+1;cout<<cs<<" "cout

17、<<endl;2.3 其他排序方法平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)希爾排序O(nlog2n)O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O (n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(n)簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O (nlog2n)O(1)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)3. 程序運(yùn)行結(jié)果 void main()srand(time(NULL);const i

18、nt num=11; /賦值int anum;int bnum;int cnum;int c1num;c0=0;a0=0;b0=0;Newarray(a,b,c);cout<<"順序數(shù)組："for(int j=1;j<num;j+)cout<<aj<<" "cout<<endl;cout<<"逆序數(shù)組："for(j=1;j<num;j+)cout<<bj<<" "cout<<endl;cout<<

19、endl;cout<<"插入排序結(jié)果為："<<"n"InsertSort(a,num);InsertSort(b,num);InsertSort(c,num);cout<<endl;Newarray(a,b,c);cout<<"希爾排序結(jié)果為："<<"n"ShellSort(a, num);ShellSort(b, num);ShellSort(c, num);cout<<endl;Newarray(a,b,c);cout<<&qu

20、ot;起泡排序結(jié)果為："<<"n"BubbleSort(a, num);BubbleSort(b, num);BubbleSort(c, num);cout<<endl;int count1=0,count2=0;Newarray(a,b,c);cout<<"快速排序結(jié)果為："<<"n"QuickSort(a,0,num-1,count1,count2);for(int i=1;i<num;i+)cout<<ai<<" "cou

21、t<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;count1=0,count2=0;QuickSort(b,0,num-1,count1,count2);for(i=1;i<num;i+)cout<<bi<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2&