計(jì)算機(jī)專業(yè)課程設(shè)計(jì)報(bào)告

數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告姓名： 學(xué)號(hào)： 5 專業(yè)： 網(wǎng)絡(luò)工程 院系： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 班級(jí)： 指導(dǎo)教師： 2011年6月15日摘要：排序的基本概念(1)排序：將無序的數(shù)據(jù)序列排列成與關(guān)鍵字有關(guān)的數(shù)據(jù)序列。2各種排序方法?希爾排序：先取第一個(gè)增量，把距離為第一個(gè)增量的倍數(shù)的記錄放在同一組中，組內(nèi)進(jìn)行直接插入排序：再取小于第一增量的第二增量，重復(fù)上述的操作。?快速排序：將原問題分解為若干個(gè)小規(guī)模的同結(jié)構(gòu)子問題，遞歸解決每個(gè)子問題。?堆排序：先把序列看成一棵大根堆或小根堆，摘取最大或最小元素后再建成新的根堆，再排序。?二路歸并排序：將兩個(gè)有序的子文件合并成一個(gè)有序文件，再擴(kuò)大子文件長(zhǎng)度，再次執(zhí)行上述操作。3．各排序法的比較?元素較大：快速排序、堆排序、歸并排序。?元素基本有序：直接插入排序、快速排序。?有益于鏈表：歸并排序。?不利于鏈表：快速排序、堆排序。?就時(shí)間性能而言，快速排序最佳。關(guān)鍵詞：排序的概念，各種排序方法，各排序法的比較英文摘要Abstract:1.Sortofbasicconceptssorting:willdisorderdatasequencearrangedandkeywordrelateddata

ernalsort:documentsinmemoryprocessing,sortingdoesnotinvolve,exchangewithinCRT.theexternalsort:sortingprocesstosaveexchangeinsideandoutside.sortingstability:ifthefiletosort,therehaveDuoGekeywordthesamerecord,aftersortwiththesamekeywordsaftertherecordoftherelativeorderbetweenremainunchanged,itsaysthesortingmethodisstable;Conversely,ifhavethesamekeywordrecordsoftherelativeorderbetweenchange,itsaysthesortingmethodisnotstable.2allkindsofsortingmethodHill:thefirsttotakethefirstorderthedistanceforincrementalfirstincrementalmultiplesofrecordsinthesamegroup,thegroupwithinthedirectinsertionsort:takeagainthenextincrementoflessthanfirstincrement,andrepeattheoperation.quicksort:willtheproblemintoseveralsmallsonwithstructure,arecursivesolveeveryproblemson.heapsort:firsttheseriesasatreerootpileoflargeorsmallrootpile,andgatheramaximumorminimumelementbuiltagainafternewrootpileof,againinorder.3.Therankingcomparisonelementbigger:quicksort,目錄TOC\o"1-5"\h\z1摘要, 1\o"CurrentDocument"2問題描述 33需求分析 34概要設(shè)計(jì) 35■數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) ?361算法設(shè)計(jì) 46.1.1快速排序 …I612一路歸并排序 >56.1.3堆排序 巧6.1.4希爾排序 …6.2算法實(shí)現(xiàn) 67.1程序測(cè)試與實(shí)驗(yàn) 107.1.1主程序- 107.1.2測(cè)試數(shù)據(jù) 117.1.3測(cè)試結(jié)果 118■性能比較 129心得體會(huì)- 13一、問題描述1．題目?jī)?nèi)容：要求分別采用快速排序、二路歸并排序、堆排序和希爾排序?qū)﹄S機(jī)生成的一組數(shù)據(jù)進(jìn)行排序（數(shù)據(jù)不少于100）；2．完成排序的輸入、輸出，比較各種排序的性能，界面友好，提供操作菜單。二、需求分析分別采用快速排序、二路歸并排序、堆排序和希爾排序?qū)﹄S機(jī)生成的一組數(shù)據(jù)進(jìn)行排序（數(shù)據(jù)不少于100）；將隨機(jī)產(chǎn)生的數(shù)據(jù)放在數(shù)組data[100]中：操作集合：intPartition(intr[],intfirst,intend)//快速排序，實(shí)現(xiàn)一次劃分voidQuickSort(intr[],intfirst,intend)//在序列first~end中遞歸地進(jìn)行快速排序voidShellSort(intr[],intn)//希爾排序voidMerge(intr[],intr1[],ints,intm,intt)//二路歸并排序voidMergePass(intr[],intr1[],intn,inth)voidsift(intr[],intk,intm)//堆排序voidheapsort(intr[],intn)四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1．元素類型intdata[]//定義數(shù)組五、算法設(shè)計(jì)1、算法分析1）、快速排序快速排序的基本思想：首先選一個(gè)軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對(duì)這兩部分重復(fù)上述方法，直到整個(gè)序列有序。需解決的關(guān)鍵問題：⑴如何選擇軸值？選擇軸值的方法：1.使用第一個(gè)記錄的關(guān)鍵碼；選取序列中間記錄的關(guān)鍵碼；比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個(gè)記錄的位置；隨機(jī)選取軸值。⑵如何實(shí)現(xiàn)分割（稱一次劃分）？解決方法：設(shè)待劃分的序列是r[s]?r[t],設(shè)參數(shù)i,j分別指向子序列左、右兩端的下標(biāo)s和t,令r[s]為軸值，（1） j從后向前掃描，直到r[j]vr[i],將r[j]移動(dòng)到r[i]的位置，使關(guān)鍵碼?。ㄍS值相比）的記錄移動(dòng)到前面去；（2） i從前向后掃描，直到r[i]>r[j],將r[i]移動(dòng)到r[j]的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動(dòng)到后面去；（3）重復(fù)上述過程，直到i=j。⑶如何處理分割得到的兩個(gè)待排序子序列？解決方法：對(duì)分割得到的兩個(gè)子序列遞歸地執(zhí)行快速排序。⑷如何判別快速排序的結(jié)束？解決方法：若待排序列中只有一個(gè)記錄，顯然已有序，否則進(jìn)行一次劃分后，再分別對(duì)分割所得的兩個(gè)子序列進(jìn)行快速排序（即遞歸處理）。2）、二路歸并排序基本思想：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長(zhǎng)度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個(gè)長(zhǎng)度為4的有序序列， ，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。需解決的關(guān)鍵問題：⑴如何將兩個(gè)有序序列合成一個(gè)有序序列？voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i<=m)while(i<=m)//收尾處理r1[k++]=r[i++]; //前一個(gè)子序列elsewhile(j<=t)r1[k++]=r[j++]; //后一個(gè)子序列}⑵怎樣完成一趟歸并？設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長(zhǎng)是2h,在歸并過程中，有以下三種情況：若iWn-2h+l,則相鄰兩個(gè)有序表的長(zhǎng)度均為h,執(zhí)行一次歸并，完成后i加2h,準(zhǔn)備進(jìn)行下一次歸并；若iVn-h+1,則表示仍有兩個(gè)相鄰有序表，一個(gè)長(zhǎng)度為h,另一個(gè)長(zhǎng)度小于h,則執(zhí)行兩個(gè)有序表的歸并,完成后退出一趟歸并。若i三n-h+1,則表明只剩下一個(gè)有序表，直接將該有序表送到r1的相應(yīng)位置,完成后退出一趟歸并。⑶如何控制二路歸并的結(jié)束？算法描述：voidMergeSort(intr[],intr1[],intn){h=1;while(h<n){MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;3）堆排序基本思想：首先將待排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。⑴如何由一個(gè)無序序列建成一個(gè)堆（即初始建堆）？算法描述：for（i=n/2;i>=1;i--）sift（r,i,n）;最后一個(gè)結(jié)點(diǎn)（葉子）的序號(hào)是n，則最后一個(gè)分支結(jié)點(diǎn)即為結(jié)點(diǎn)n的雙親，其序號(hào)是n/2。⑵如何處理堆頂記錄？解決方法：第i次處理堆頂是將堆頂記錄r［1］與序列中第n-i+1個(gè)記錄r［n-i+l］交換。⑶如何調(diào)整剩余記錄，成為一個(gè)新堆（即重建堆）？解決方法：第i次調(diào)整剩余記錄，此時(shí)，剩余記錄有n-i個(gè)，調(diào)整根結(jié)點(diǎn)至第n-i個(gè)記錄。4）希爾排序基本思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，對(duì)全體記錄進(jìn)行直接插入排序。（1） 應(yīng)如何分割待排序記錄，才能保證整個(gè)序列逐步向基本有序發(fā)展？解決方法：將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。增量應(yīng)如何?。肯栕钤缣岢龅姆椒ㄊ莇1=n/2，di+1=di/2。（2） 子序列內(nèi)如何進(jìn)行直接插入排序？解決方法：在插入記錄r［i］時(shí)，自r［i-d］起往前跳躍式（跳躍幅度為d）搜索待插入位置，并且r［只是暫存單元，不是哨兵。當(dāng)搜索位置VO,表示插入位置已找到。在搜索過程中，記錄后移也是跳躍d個(gè)位置。在整個(gè)序列中，前d個(gè)記錄分別是d個(gè)子序列中的第一個(gè)記錄，所以從第d+1個(gè)記錄開始進(jìn)行插入。2、算法實(shí)現(xiàn)#include"stdafx.h"#include<iostream>#include<iomanip>usingnamespacestd;//快速排序intPartition(intr[],intfirst,intend)//實(shí)現(xiàn)一次劃分{inttemp,i,j;i=first;j=end; //初始化while(i<j){while(i<j&&r[i]<=r[j])j--;//右側(cè)掃描if(i<j){temp=r[i];r[i]=r[j];r[j]=temp;i++;//將較小記錄交換到前面}while(i<j&&r[i]<=r[j])i++;//左側(cè)掃描if(i<j){temp=r[j];r[j]=r[i];r[i]=temp;j--;//將較大記錄交換到后面}}returni; //i為軸值記錄的最終位置}voidQuickSort(intr[],intfirst,intend){//在序列first~end中遞歸地進(jìn)行快速排序if(first<end){intpivotpos=Partition(r,first,end);Quicksort(r,first,pivotpos-1);//對(duì)前一個(gè)子序列進(jìn)行快速排序QuickSort(r,pivotpos+1,end);//對(duì)后一個(gè)子序列進(jìn)行快速排序}//希爾排序voidShellSort(intr[],intn){for(intd=n/2;d>=1;d=d/2){for(inti=d+l;i〈二n;i++) //將r[i]插入到所屬的子序列中{intj;r[0]=r[i]; //暫存待插入記錄j=i-d; //j指向所屬子序列的最后一個(gè)記錄while(j>0&&r[0]〈r[j]){r[j+d]=r[j]; //記錄后移d個(gè)位置j=j-d; //比較同一子序列的前一個(gè)記錄}r[j+d]=r[0];}}}//二路歸并排序voidMerge(intr[],intrl[],ints,intm,intt){inti=s,j=m+l,k=s;while(i〈=m&&j〈=t){if(r[i]〈=r[j]) rl[k++]=r[i++];elserl[k++]=r[j++];}if(i〈=m)while(i〈=m) //收尾處理rl[k++]=r[i++]; //前一個(gè)子序列elsewhile(j〈=t)rl[k++]=r[j++]; //后一個(gè)子序列}voidMergePass(intr[],intrl[],intn,inth){inti=l;while(i〈=n-2*h+l) //情況{Merge(r,rl,i,i+h-l,i+2*h-l);i+=2*h;//情況if(i<n-h+1)Merge(r,r1,i,i+h-1,n);elsefor(intk=i;k<=n;k++)//情況r1[k]=r[k];//情況}voidMergeSort(intr[],intr1[],intn){inth=1;while(h<n){MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;}}//堆排序voidsift(intr[],intk,intm){inti,j,x;intt;boolfinished;i=k;j=2*i;t=r[k];x=t;finished=false;while((j<=m)&&(!finished)){if((j<m)&&(r[j]>r[j+1]))j=j+1;if(x<=r[j])finished=true;else{r[i]=r[j];i=j;j=2*i;};};r[i]=t;}voidheapsort(intr[],intn){inti,m;intt;m=n/2;for(i=m;i>=1;i--)sift(r,i,n);for(i=n;i>=2;i--){t=r[1];r[1]=r[i];r[i]=t;sift(r,1,i-1);}}intmain(){intdata[101],data1[101],data2[100],c;cout〈〈"隨機(jī)產(chǎn)生個(gè)隨機(jī)數(shù)為"〈〈endl;for(inti=1;i<=100;i++)data[i]=10+rand()%(500);for(inti=1;i〈=100;i++)cout〈〈data[i]〈〈"";cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";for(inti=0;i〈100;i++)while(1){cout〈〈"0：快速排序\n";cout〈〈"1:希爾排序\n";cout〈〈"2:二路歸并排序\n";cout〈〈"3:堆排序\n";cout〈〈"4：退出\n";cout〈〈"請(qǐng)輸入(0--4):\n"cin>>c;switch(c){case0:QuickSort(data,1,100);cout〈〈"快速排序后的序列為:"〈〈endl;for(inti=1;i〈=100;i++){cout〈〈data[i]〈〈"";}cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";break;case1:ShellSort(data,100);cout〈〈"希爾排序后的序列為:"〈〈endl;for(inti=1;i〈=100;i++){cout〈〈data[i]〈〈"";}cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";break;case2:MergeSort(data,data1,100);cout〈〈"二路歸并排序后的序列為:"〈〈endl;for(inti=0;i〈100;i++){cout〈〈data[i]〈〈"";}cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";break;case3:heapsort(data,100);cout〈〈"堆排序后的序列為:"〈〈endl;for(inti=1;i〈=100;i++){cout<<data[i]<<"";}cout<<endl;break;case4:return0;break;}}return0;}六、程序測(cè)試與實(shí)現(xiàn)1、主程序voidmain()//{intdata[101],data1[101],data2[100],c;cout〈〈"隨機(jī)產(chǎn)生個(gè)隨機(jī)數(shù)為"〈〈endl;for(inti=1;i<=100;i++)data[i]=10+rand()%(500);for(inti=1;i〈=100;i++)cout〈〈data[i]〈〈"";cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";for(inti=0;i〈100;i++)while(1){cout〈〈"0：快速排序\n";cout〈〈"1:希爾排序\n"cout〈〈"2:二路歸并排序\n"cout〈〈"3:堆排序\n"cout〈〈"4：退出\n";cout〈〈"請(qǐng)輸入(0--4): \n";cin>>c;}3、測(cè)試數(shù)據(jù)i陰個(gè)隨機(jī)數(shù)為題MiillW織iBf曲量眶W徳璉丫龜詼腫f繞rut旳8腎■嘶甲*tlMMif；y-￡jt-Miiit-MMflcMl?l?g}M?MiTSlfcWtMjlffMM：MBWM■umtijyw』;wwwm?1乂?2674736?2332513?38S336S16ill4335848128?243?51454S421328S3264513?133?4星并排非'■■-序速奮番曙二堆退4、測(cè)試結(jié)果二塔歸并排序后的序列為:GHGi&1G3?45454747484850ElE11511541552512632&G34435335244144&4491581S31721741771791832672742812883633683693784524524544GG2912583@23793S03S64G74￡4471E758929430?3?24722133154朗4?4215318401476ill221321403477114嘟二塔歸并排序后的序列為:GHGi&1G3?45454747484850ElE11511541552512632&G34435335244144&4491581S31721741771791832672742812883633683693784524524544GG2912583@23793S03S64G74￡4471E758929430?3?24722133154朗4?4215318401476ill221321403477114嘟32&4044SS1162233324跖501128233333412133234337422126236337431139239343439Xcl[Bj：]sei485332228倔4043262264774033212214764813182154744S83152134723?2

36?2能47138G3821834&4鈿砂2￥817?4573?9291

1??4563?82881?44543692811724b23682?41S345236026?15844935226615544e35626315444134425115143934323913943133?236136422337234133949258S?5151504S4S474745453916IS肉速排序后的序列対2細(xì).1639454547474849；>0515157■5892:94ill1141161281331361391511541551581631721741??1??1832S0213215221226228233234Z36239251迪266267274281Z昵2?12?83K23R9315313321326