上傳人：文***

認證信息

認證類型：個人認證

認證主體：黃**（實名認證）

IP屬地：廣東

IP屬地：廣東 上傳時間：2022-03-06 格式：DOC 頁數(shù)：15 大?。?47.03KB 積分：20 舉報 版權(quán)申訴

1、word數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱： 實驗四排序?qū)W生姓名：XX班 級：班內(nèi)序號：學(xué) 號： 日 期： 1實驗要求實驗?zāi)康模和ㄟ^選擇實驗內(nèi)容中的兩個題目之一，學(xué)習(xí)、實現(xiàn)、比照、各種排序的算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。題目1：使用簡單數(shù)組實現(xiàn)下面各種排序算法，并進行比擬。排序算法如下：1、 插入排序；2、 希爾排序；3、 冒泡排序；4、 快速排序；5、 簡單項選擇擇排序；6、 堆排序；7、 歸并排序；8、 基數(shù)排序選作；9、 其他。具體要求如下：1、 測試數(shù)據(jù)分成三類：正序、逆序、隨機數(shù)據(jù)。2、 對于這三類數(shù)據(jù)，比擬上述排序算法中關(guān)鍵字的比擬次數(shù)和移動次數(shù)其中關(guān)鍵字交換記為3次

2、移動。3、 對于這三類數(shù)據(jù)，比擬上述排序算法中不同算法的執(zhí)行時間，精確到微妙。4、 對2和3的結(jié)果進行分析，驗證上述各種算法的時間復(fù)雜度。5、 編寫main函數(shù)測試各種排序算法的正確性。2. 程序分析2.1 存儲結(jié)構(gòu)存儲結(jié)構(gòu)：數(shù)組0A11A22A33A44A55A6NAn-12.2 關(guān)鍵算法分析一、關(guān)鍵算法：1、插入排序a、 取排序的第二個數(shù)據(jù)與前一個比擬b、 假設(shè)比前一個小，那么賦值給哨兵c、 從后向前比擬，將其插入在比其小的元素后d、 循環(huán)排序2、希爾排序a、 將數(shù)組分成兩份b、 將第一份數(shù)組的元素與哨兵比擬c、 假設(shè)其大與哨兵，其值賦給哨兵d、 哨兵與第二份數(shù)組元素比擬，將較大的值賦給第

3、二份數(shù)組e、 循環(huán)進行數(shù)組拆分3、對數(shù)據(jù)進行編碼a、 取數(shù)組元素與下一個元素比擬b、 假設(shè)比下一個元素大，那么與其交換c、 后移，重復(fù)d、 改變總元素值，并重復(fù)上述代碼4、快速排序a、 選取標準值b、 比擬上下指針指向元素，假設(shè)指針保持前后順序，且后指針元素大于標準值，后指針前移，重新比擬c、 否那么后面元素賦給前面元素d、 假設(shè)后指針元素小于標準值，前指針后移，重新比擬e、 否那么前面元素賦給后面元素5、簡單項選擇擇排序a、 從數(shù)組中選擇出最小元素b、 假設(shè)不為當前元素，那么交換c、 后移將當前元素設(shè)為下一個元素6、堆排序a、 生成小頂堆b、 將堆的根節(jié)點移至數(shù)組的最后c、 去掉已做過根節(jié)點

4、的元素繼續(xù)生成小頂堆d、 數(shù)組倒置7、歸并排序a、 將數(shù)組每次以1/2拆分，直到為最小單位b、 小相鄰單位數(shù)組比擬重排合成新的單位c、 循環(huán)直至完成排序二、代碼詳細分析：1、插入排序關(guān)鍵代碼： 取排序的第二個數(shù)據(jù)與前一個比擬：if(ri<ri-1) 假設(shè)比前一個小，那么賦值給哨兵：r0=ri; 從后向前比擬，將其插入在比其小的元素后：for(j=i-1;r0<rj;j-)rj+1=rj;a+; rj+1=r0; 循環(huán)排序2、希爾排序關(guān)鍵代碼： 將數(shù)組分成兩份：d=n/2 將第一份數(shù)組的元素與哨兵比擬：for(int i=d+1;i<=n;i+) 假設(shè)其大與哨兵，其值賦給哨兵：

5、if(r0<ri-d) r0=ri; 哨兵與第二份數(shù)組元素比擬，將較大的值賦給第二份數(shù)組：for(j=i-d;j>0&&r0<rj;j=j-d) rj+d=rj; 循環(huán)進行數(shù)組拆分：for(int;d>=1;d=d/2) 3、冒泡排序關(guān)鍵代碼： 取數(shù)組元素與下一個元素比擬： for(int i=1;i<bound;i+)if(ri>ri+1) 假設(shè)比下一個元素大，那么與其交換： r0=ri; ri=ri+1; ri+1=r0; 后移，重復(fù)：for(int i=1;i<bound;i+) 改變總元素值，并重復(fù)上述代碼：int bound=

6、pos; 4、快速排序關(guān)鍵代碼： 選取標準值：r0=ri 比擬上下指針指向元素，假設(shè)指針保持前后順序，且后指針元素大于標準值，后指針前移，重新比擬：while(i<j&&rj>=flag) j-; 否那么后面元素賦給前面元素：ri=rj; 假設(shè)后指針元素小于標準值，前指針后移，重新比擬：while(i<j&&ri<=flag) i+; 否那么前面元素賦給后面元素：rj=ri;5、簡單項選擇擇排序關(guān)鍵代碼： 從數(shù)組中選擇出最小元素： for(int j=i+1;j<=n;j+) if(rj<rindex) index=j; 假設(shè)

7、不為當前元素，那么交換： if(index!=i) r0=ri; ri=rindex; rindex=r0; 后移將當前元素設(shè)為下一個元素：for(int i=1;i<n;i+)6、堆排序關(guān)鍵代碼： 生成小頂堆：while(j<=m) if(j<m&&rj>rj+1) j+; if(ri<rj) break; else int x; x=ri; ri=rj; rj=x; i=j; j=2*i; 將堆的根節(jié)點移至數(shù)組的最后： x=r1; r1=rn-i+1; rn-i+1=x; 去掉已做過根節(jié)點的元素繼續(xù)生成小頂堆：sift(r,1,n-i,x,y)

8、; 數(shù)組倒置輸出: for(int i=n;i>0;i-)cout<<ri<<" "7、歸并排序關(guān)鍵代碼： 將數(shù)組每次以1/2拆分，直到為最小單位： mid=(low+high)/2; 小相鄰單位數(shù)組比擬重排合成新的單位： while(i<=m&&j<=high) if(L.ri<=L.rj) tk+=L.ri+; else tk+=L.rj+; while(i<=m) tk+=L.ri+; while(j<=high) tk+=L.rj+; for(i=low,k=0;i<=high;i+,

9、k+) L.ri=tk; 三、計算關(guān)鍵算法的時間、空間復(fù)雜度插入排序On2希爾排序On2冒泡排序On2快速排序Onlog2n簡單項選擇擇排序On2堆排序Onlog2n歸并排序Onlog2n3. 程序運行結(jié)果1、 測試主函數(shù)流程：流程圖如下圖流程圖示意圖程序運行結(jié)果圖如下：2、 測試條件：按題目要求分別輸入同組數(shù)據(jù)的正序、逆序、隨機序列進行測試。3、 測試結(jié)論：不同的排序方法移動次數(shù)比擬次數(shù)和所用時間都是有所區(qū)別的。4. 總結(jié)調(diào)試時出現(xiàn)的問題及解決的方法：在調(diào)試時，開始在歸并排序的時候，雖然代碼編譯成功，但調(diào)試出現(xiàn)了錯誤，通過逐步調(diào)試發(fā)現(xiàn)是由于發(fā)生了地址沖突。因此將原本的直接調(diào)用數(shù)組改成了結(jié)構(gòu)體

10、數(shù)組，通過引用來實現(xiàn)歸并排序，最終獲得了成功心得體會：學(xué)習(xí)、實現(xiàn)、比照、各種排序的算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況下一步的改良：改良計數(shù)器，尋找其他排序方式。附：源代碼#include<iostream>using namespace std; int Cnum = 0; int Mnum = 0;class LEDprivate :int compare;int move;public:void InsertSort(int r , int n) ;/直接插入排序void ShellInsert(int r,int n) ;/希爾排序void BubbleSo

11、rt(int r,int n);/冒泡排序void Qsort(int r,int i,int j);/快速排序void SelectSort(int r,int n);/選擇排序void HeapSort (int r,int n);void MergePass(int r,int r1,int n ,int h);int Partion(int r ,int first ,int end );void Sift(int r,int k , int m);void Merge(int r,int r1,int s,int m,int t);void LED:InsertSort(int r

12、, int n) /插入排序 compare = 0;move = 0;for(int i=2;i<=n;i+) if(ri<ri-1) r0=ri; move +; ri=ri-1;move +; int j; for(j=i-2;r0<rj;j-) compare+; rj+1=rj; move +; +compare; rj+1=r0;move +; +compare;for(int i=1;i<=n;i+)cout<<ri<<" "cout<<"比擬次數(shù)為"<<compare

13、 <<" ; 移動次數(shù)為"<<move<<" ;"void LED:ShellInsert(int r,int n) /希爾排序compare = 0;move = 0;for(int d=n/2;d>=1;d=d/2) for(int i=d+1;i<=n;i+) if(ri<ri-d) move+; r0=ri;int j; for(j=i-d;j>0&&r0<rj;j=j-d)rj+d=rj;move+;compare+; rj+d=r0;move+;compare+

14、;for(int i=1;i<=n;i+) cout<<ri<<" "cout<<"比擬次數(shù)為"<<compare <<" ; 移動次數(shù)為"<<move<<" ;"void LED:BubbleSort(int r,int n) /冒泡排序改良compare = 0;move = 0;int pos = n ;while(pos != 0)int bound = pos;pos = 0;for(int i =1;i <b

15、ound ; i+)compare +;if(ri>ri+1)r0 = ri; ri = ri+1;ri+1 = r0; /交換pos = i;move=move+3;for(int i=1;i<=n;i+)cout<<ri<<" "cout<<"比擬次數(shù)為"<<compare <<" ; 移動次數(shù)為"<<move<<" ;"int LED:Partion(int r ,int first ,int end )int i

16、 = first ; /分區(qū)的左界int j = end; /分區(qū)的右界int pivot = ri; /保存第一個元素，作為基準元素while(i < j)while(i<j)&&(rj>=pivot) /右側(cè)掃描，尋找<pivot的元素前移j - ;Cnum+;ri = rj ;while(i<j)&&(ri<=pivot ) /左側(cè)掃描，尋找>pivot的元素后移i +;Cnum+;rj = ri;ri = pivot ; /將軸值移動到i=j的位置return i; /返回分區(qū)的分界值ivoid LED:Qsor

17、t(int r,int i,int j)if(i < j) Mnum +;int pivotloc = Partion(r,i,j);Qsort (r,i,pivotloc -1); /左分區(qū)快速排序Qsort (r,pivotloc +1,j); / 右分區(qū)快速排序elsevoid LED:SelectSort(int r,int n) /簡單項選擇擇排序compare = 0;move = 0;for(int i =1 ; i <n ; i+) /n-1趟排序int index = i; /查找最小記錄的位置indexfor(int j = i + 1;j<=n;j+)c

18、ompare+;if(rj<rindex)index = j;if(index != i) /假設(shè)第一就是最小元素，那么不用交換r0 = ri;ri = rindex;rindex = r0; /利用r0，作為臨時空間交換記錄move+=3;for(int i=1;i<=n;i+)cout<<ri<<" "cout<<"比擬次數(shù)為"<<compare <<" ; 移動次數(shù)為"<<move<<" ;"/*void LED:

19、Sift(int r,int k , int m)int i = k, j = 2*i;while(j<=m)if(j<m&&rj<rj+1)j+;if(ri>=rj)break;elser0 = ri;ri = rj;rj = r0;i = j ; j = 2* i;void LED:HeapSort (int r,int n)for(int i = n/2; i >= 1 ; i-) /建堆Sift(r,i,n);for(int i = n;i>1;i-) /堆排序r0 = r1; r1 = ri;ri= r0; /輸出堆頂元素Sift(

20、r,1,i-1); /重建堆void LED: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+;elser1k+ = rj+;while(i<=m)r1k+ = ri+;while(j<=t)r1k+ = rj+;void LED:MergePass(int r,int r1,int n ,int h)int i = 1;while(i<=n-2*h+1)Merge (r ,r1,

21、i,i+h-1,i+2*h-1);i+= 2*h;if(i<n-h+1)Merge (r,r1,i,i+h-1,n);elsefor(;i<=n;i+)r1i = ri;*/void main()int r110000,r210000,r310000;int R10000;char y ;int j=0;cout<<"請輸入元素個數(shù)："<<endl;cin>>j;cout<<"請輸入將要排序的元素(正序)："<<endl;for(int i=1;i<=j;i+)cin>&

22、gt;r1i;cout<<"請輸入將要排序的元素(逆序)："<<endl;for(int i=1;i<=j;i+)cin>>r2i;cout<<"請輸入將要排序的元素亂序："<<endl;for(int i=1;i<=j;i+)cin>>r3i;cout<<endl;LED l;for(int i= 1;i<=j;i+)Ri=r1i;cout<<"直接插入排序正序輸出結(jié)果："l.InsertSort(R,j);cout&l

23、t;<endl;for(int i= 1;i<=j;i+)Ri=r2i;cout<<"直接插入排序逆序輸出結(jié)果："l.InsertSort(R,j); cout<<endl;for(int i= 1;i<=j;i+)Ri=r3i;cout<<"直接插入排序亂序輸出結(jié)果："l.InsertSort(R,j);cout<<endl; for(int i= 1;i<=j;i+)Ri=r1i;cout<<"希爾排序正序輸出結(jié)果："l.ShellInsert(R

24、,j);cout<<endl;for(int i= 1;i<=j;i+)Ri=r2i;cout<<"希爾排序逆序輸出結(jié)果："l.ShellInsert(R,j);cout<<endl;for(int i= 1;i<=j;i+)Ri=r3i;cout<<"希爾排序亂序輸出結(jié)果："l.ShellInsert(R,j);cout<<endl;for(int i= 1;i<=j;i+)Ri=r1i;cout<<"冒泡排序正序輸出結(jié)果："l.BubbleS

25、ort(R,j);cout<<endl;for(int i= 1;i<=j;i+)Ri=r2i;cout<<"冒泡排序逆序輸出結(jié)果："l.BubbleSort(R,j);cout<<endl;for(int i= 1;i<=j;i+)Ri=r3i;cout<<"冒泡排序亂序輸出結(jié)果："l.BubbleSort(R,j);cout<<endl;for(int i= 1;i<=j;i+)Ri=r1i;cout<<"快速排序正序輸出結(jié)果："l.Qsort(R,1,j);for(int k=1;k<=j;k+)cout<<Rk<<" "cout<<"比擬次數(shù)為"<<Cnum <<" ; 移動次數(shù)為"<<Mnum<<" "Cnum = 0;Mnum = 0;cout<<en