排序問題實驗報告

2010級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：排序姓名：袁彬班級：2009211120班內(nèi)序號：09學(xué)號：09210552日期：2010年12月19日1．實驗要求試驗?zāi)康模和ㄟ^選擇試驗內(nèi)容中的兩個題目之一，學(xué)習(xí)、實現(xiàn)、對比各種排序的算法，掌握各種排序算法的優(yōu)缺點，以及各種算法使用的情況。試驗內(nèi)容：題目一：使用簡單數(shù)組實現(xiàn)下面各種排序算法，并進行比較。排序算法如下：①插入排序；②希爾排序③冒泡排序；④快速排序；⑤簡單選擇排序；⑥堆排序⑦歸并排序⑧基數(shù)排序⑨其他。具體要求如下：①測試數(shù)據(jù)分為三類：正序，逆序，隨機數(shù)據(jù)。②對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換記為三次移動）。③對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微妙。④對②和③的結(jié)果進行分析，驗證上述各種算法的時間復(fù)雜度。⑤編寫main()函數(shù)測試各種排序算法的正確性。題目二：使用鏈表實現(xiàn)下面各種排序算法，并進行比較。排序算法如下：①插入排序；②冒泡排序；③快速排序；④簡單選擇排序；⑤其他。具體要求如下：①測試數(shù)據(jù)分為三類：正序，逆序，隨機數(shù)據(jù)。②對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換記為三次移動）。③對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微妙（選作）④對②和③的結(jié)果進行分析，驗證上述各種算法的時間復(fù)雜度。⑤編寫main()函數(shù)測試各種排序算法的正確性。2.程序分析2.1存儲結(jié)構(gòu)程序中每一個算法均是用一個類來表示的，類中有自己的構(gòu)造函數(shù)、排序函數(shù)。程序的儲存結(jié)構(gòu)采用數(shù)組。數(shù)組的第一個位置不存儲數(shù)據(jù)。數(shù)據(jù)從第二個位置開始。數(shù)組中的相對位置為數(shù)組的下標(biāo)。2.2關(guān)鍵算法分析㈠、關(guān)鍵算法：1、插入排序函數(shù)：Insertsort(intn)①、從2開始做循環(huán)，依次和前面的數(shù)進行比較：for(inti=2;i<=n;i++)②、如果后面的比前面的小，則進行前移：if(number[i]<number[i-1])③、設(shè)置哨兵：number[0]=number[i];④、如果后面的比前面的小，前面的進行后移：for(j=i-1;number[0]<number[j];j--)⑤、前面的進行后移：number[j+1]=number[j];⑥、將比較的數(shù)據(jù)放置到正確位置：number[j+1]=number[0];2、希爾排序函數(shù)：Shellinsert(intn)①、以長度的一半為間隔進行循環(huán)：for(intd=n/2;d>=1;d=d/2)②、在自己的間隔中進行簡單插入排序，進行循環(huán)：for(inti=d+1;i<=n;i++)③、如果后面的數(shù)據(jù)比前面的小，進行前移：if(number[i]<number[i-d])④、設(shè)置哨兵：number[0]=number[i];⑤、在自己的間隔中進行簡單插入排序：for(j=i-d;number[0]<number[j]&&j>0;j=j-d)⑥、大的數(shù)據(jù)后移：number[j+d]=number[j];⑦、哨兵歸位：number[j+d]=number[0];3、冒泡排序函數(shù)：Bubblesort(intn)①、設(shè)置有序無序的邊界點：intpos=n;②、當(dāng)邊界點不為空進行循環(huán)：while(pos!=0)③、邊界點傳遞給bound：intbound=pos;④、從開始到邊界點進行循環(huán)：for(inti=1;i<bound;i++)⑤、如果前面的數(shù)據(jù)比后面的大，進行交換：if(number[i]>number[i+1])⑥、交換：number[0]=number[i];number[i]=number[i+1];number[i+1]=number[0];⑦、從小設(shè)置邊界點：pos=i;4、一趟快速排序函數(shù)：partion(intfirst,intend)①、傳遞設(shè)置整個數(shù)據(jù)的起點和終點：inti=first;intj=end;②、設(shè)置中軸：number[0]=number[i];③、當(dāng)end大于first進行循環(huán)：while(i<j)④、當(dāng)后面的數(shù)據(jù)大于中軸，后面的游標(biāo)前移：while((i<j)&&(number[j]>=number[0])) j--;⑤、中軸和比它大的數(shù)據(jù)進行交換：number[i]=number[j];⑥、當(dāng)前面的數(shù)據(jù)小于中軸，前面的游標(biāo)后移：while((i<j)&&(number[i]<=number[0]))i++;⑦、中軸和比它小的數(shù)據(jù)進行交換：number[j]=number[i];⑧、將中軸進行歸位：number[i]=number[0];5、遞歸快速排序函數(shù)：Qsort(inti,intj)①、如果數(shù)組不為空，進行排序：if(i<j)②、一趟冒泡排序：intpivotloc=partion(i,j);③、遞歸將左右半面進行排序：Qsort(i,pivotloc-1);Qsort(pivotloc+1,j);6、簡單選擇排序函數(shù)：Selectsort(intn)①、從數(shù)組開始到結(jié)尾進行遍歷：for(inti=1;i<n;i++)②、設(shè)置最小數(shù)據(jù)標(biāo)記：intindex=i;③、在無序區(qū)進行循環(huán)：for(intj=i+1;j<=n;j++)④、當(dāng)出現(xiàn)比標(biāo)記還小的數(shù)據(jù)，就進行交換：if(number[j]<number[index])index=j;⑤、如果最小的不是末尾的數(shù)，就進行交換：if(index!=i)⑥、進行交換： number[0]=number[i];number[i]=number[index];number[index]=number[0];7、一趟堆排序函數(shù)：sift(intk,intm)①、設(shè)置根節(jié)點和孩子的位置：inti=k,j=2*k;②、從左右孩子中選擇出最小的孩子：if(j<m&&number[j]>number[j+1])j++;③、判斷根節(jié)點是不是最小的，不是就進行交換：if(number[i]<number[j])break;④、進行交換：number[0]=number[i];number[i]=number[j];number[j]=number[0];⑤、將根節(jié)點和孩子位置后移，繼續(xù)排序：i=j;j=2*i;8、遞歸堆排序函數(shù)：Heapsort(intn)①、從最大非葉子節(jié)點，進行一趟堆排序：for(i=n/2;i>=1;i--)②、進行數(shù)組長度值的循環(huán)：for(i=1;i<n;i++)③、將根節(jié)點和尾節(jié)點進行交換：number[0]=number[1];number[1]=number[n-i+1];number[n-i+1]=number[0];④、在進行一趟堆排序：sift(1,n-i);9、一趟歸并排序函數(shù)：Merge(int*r,int*r1,ints,intm,intt)①、傳遞設(shè)置兩個數(shù)組的起點和終點：inti=s;intj=m+1;intk=s;②、當(dāng)任意一個數(shù)組沒有達到終點時，進行循環(huán)：while(i<=m&&j<=t)③、進行循環(huán)，將較小的值傳給r1數(shù)組：if(r[i]<r[j])④、將較小的值傳給r1數(shù)組：r1[k++]=r[i++];elser1[k++]=r[j++];⑤、當(dāng)一個數(shù)字已經(jīng)比較完，做循環(huán)將其續(xù)借到r1數(shù)組中：if(i<=m)while(i<=m)r1[k++]=r[i++];⑤、當(dāng)另一個數(shù)字已經(jīng)比較完，做循環(huán)將其續(xù)借到r1數(shù)組中：if(j<=t)while(j<=t)r1[k++]=r[j++];10、遞歸歸并排序函數(shù)：MergeSort(int*r,int*r1,ints,intt)①、創(chuàng)建新數(shù)字指針存儲排序序列：int*r2=newint[t];②、當(dāng)序列中只有一個數(shù)據(jù)時，令其相等：if(s==t)r1[s]=r[s];③、否則，進行遞歸：else④、將原數(shù)組折半：intm=(s+t)/2;⑤、將前半數(shù)組進行遞歸調(diào)用：MergeSort(r,r2,s,m);⑥、將后半數(shù)組進行遞歸調(diào)用：MergeSort(r,r2,m+1,t);⑦、將數(shù)組進行遞歸調(diào)用：Merge(r2,r1,s,m,t);㈡、關(guān)鍵算法的時間、空間復(fù)雜度①、直接插入排序函數(shù)：時間復(fù)雜度O（n2）②、希爾排序函數(shù)：時間復(fù)雜度O(n㏒2n)③、起泡排序：時間復(fù)雜度O（n2）④、快速排序：時間復(fù)雜度O(n㏒2n)⑤、簡單選擇排序：時間復(fù)雜度O（n2）⑥、堆排序：時間復(fù)雜度O(n㏒2n)⑦、歸并排序：時間復(fù)雜度O(n㏒2n)3.程序運行結(jié)果測試主函數(shù)流程：程序流程圖如下：開始 開始輸入要排序的整數(shù)個數(shù)輸入要排序的整數(shù)個數(shù)n手工輸入按手工輸入按’a’;隨機產(chǎn)生按’b’ b隨機產(chǎn)生n個整數(shù)手工輸入n個整數(shù) 隨機產(chǎn)生n個整數(shù)手工輸入n個整數(shù)直接插入排序直接插入排序希爾排序希爾排序氣泡排序氣泡排序快速排序快速排序簡單排序簡單排序堆排序堆排序歸并排序歸并排序結(jié)束結(jié)束4.總結(jié)（1）、出現(xiàn)的問題及調(diào)試的方法 這次試驗總的來說是比較簡單的，因為這七種排序算法的代碼書上都有，在理解的基礎(chǔ)上參考書上的代碼輸入基本上不會有太大的問題，但問題還是有的。例如：一組待排序的整數(shù)存在一個數(shù)組中，當(dāng)采用一種排序算法對這個數(shù)組進行排序后，數(shù)組就被修改了，變?yōu)橛行虻男蛄?，這是一個問題，于是我動態(tài)申請了七個數(shù)組，每次排序?qū)Σ煌臄?shù)組進行，這個問題就解決了（2）、心得體會這次試驗是我對排序運算有了深刻的理解，對我們課堂上的知識進行回顧。在程序編譯和鏈接時還報了一些錯，最后我對排序運算有了深刻的理解，對我們課堂上的知識進行回顧。在程序編譯和鏈接時還報了一些錯，最后通過一步一步的測試，也很快解決了問題。通過這次程序我感覺我對C++調(diào)試有個很深的理解，對程序的調(diào)試有了很多心得，也對我的程序調(diào)試和編寫有了進一步的提高。同