分治法實(shí)現(xiàn)一組無(wú)序序列的兩路合并排序和快速排序

1、實(shí)驗(yàn)報(bào)告（ 2011/2012 學(xué)年 第一學(xué)期）課程名稱算法分析與設(shè)計(jì)A實(shí)驗(yàn)名稱分治策略實(shí)驗(yàn)時(shí)間年月日指導(dǎo)單位計(jì)算機(jī)學(xué)院軟件工程系指導(dǎo)教師學(xué)生姓名學(xué)院 (系)班級(jí)學(xué)號(hào)專業(yè)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱分治策略指導(dǎo)教師實(shí)驗(yàn)類型驗(yàn)證實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間一、實(shí)驗(yàn)?zāi)康暮腿蝿?wù)理解分治法的算法思想，閱讀實(shí)現(xiàn)書上已有的部分程序代碼并完善程序，加深對(duì)分治法的算法原理及實(shí)現(xiàn)過(guò)程的理解。用分治法實(shí)現(xiàn)一組無(wú)序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理， 編程實(shí)現(xiàn)分別用這兩種方法將輸入的一組無(wú)序序列排序?yàn)橛行蛐蛄泻筝敵?。二、?shí)驗(yàn)環(huán)境 (實(shí)驗(yàn)設(shè)備 )VC+6.0三、實(shí)驗(yàn)原理及內(nèi)容 （包括操作過(guò)程、結(jié)果分析等）實(shí)

2、驗(yàn)原理1、排序是數(shù)據(jù)處理中常用的重要手段，是指將一個(gè)元素序列調(diào)整為按指定關(guān)鍵字值的遞增（或遞減）次序排列的有序序列。用分治法求解排序問(wèn)題的思路是，按某種方式將序列分成兩個(gè)或多個(gè)子序列，分別進(jìn)行排序，再將已排序的子序列合并成一個(gè)有序序列。合并排序和快速排序是兩種典型的符合分治策略的排序算法。2、如果采用順序存儲(chǔ)的可排序表作為算法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，則需要定義一個(gè)可排序表類 SortableList，兩路合并算法和快速排序算法均由定義在該類上的函數(shù)實(shí)現(xiàn)。其中Input 函數(shù)和 Output 函數(shù)分別用于向可排序表中輸入待排序序列，以及輸出已經(jīng)排序好的序列。3、兩路合并排序算法的基本思想是：將待排序元素

3、平分成大小大致相同的兩個(gè)子序列，然后對(duì)每個(gè)子序列分別使用遞歸的方法進(jìn)行兩路合并排序，直到子序列長(zhǎng)度變?yōu)?，最后利用合并算法將得到的已排序好的兩個(gè)子序列合并成一個(gè)有序的序列。兩路合并排序算法的核心部分是將子問(wèn)題的解組合成原問(wèn)題解得合并操作。常用的操作是新建一個(gè)序列，序列的大小等于要合并的兩個(gè)子序列的長(zhǎng)度之和。比較兩個(gè)子序列中的最小值，輸出其中較小者到新建的序列中，重復(fù)此過(guò)程直到其中一個(gè)子序列為空。如果另一個(gè)子序列中還有元素未輸出，則將剩余元素依次輸出到新建序列中即可。最終得到一個(gè)有序序列。4、結(jié)合書上已有的程序代碼， 使用分治法的快速排序算法， 實(shí)現(xiàn)對(duì)初始序列的排序?？焖倥判蛩惴ǖ幕舅枷胧牵海?/p>

4、1）在待排序序列Kleft:right 上選擇一個(gè)基準(zhǔn)元素（通常是最左邊的元素Kleft ），通過(guò)一趟分劃操作將序列分成左右兩個(gè)子序列，左子序列中所有元素都小于等于該基準(zhǔn)元素，有子序列中所有元素都大于等于該基準(zhǔn)元素。則當(dāng)前基準(zhǔn)元素所在的位置位于左、右子序列的中間，即是其排序完成后的最終位置。（2）通過(guò)遞歸調(diào)用，對(duì)左子序列和右子序列再分別進(jìn)行快速排序算法的調(diào)用。（3）由于每一趟分劃結(jié)束后， 左子序列中的元素均不大于基準(zhǔn)元素，右子序列中的元素均不小于基準(zhǔn)元素。而每次分劃后，對(duì)分劃得到的左、右子序列的快速排序又均是就地進(jìn)行，所以一旦左、右兩個(gè)子序列都已分別排好序后，無(wú)需再執(zhí)行任何計(jì)算，整個(gè)序列就是所

5、要求的有序序列了。因此類中應(yīng)定義成員函數(shù)QuickSort 來(lái)完成遞歸快速排序算法的調(diào)用和成員函數(shù)5、比較合并排序和兩種算法的異同。問(wèn)題分解過(guò)程：合并排序?qū)⑿蛄幸环譃槎纯?。（十分?jiǎn)單）快速排序需調(diào)用 Partition 函數(shù)將一個(gè)序列劃分為子序列。 （分解方法相對(duì)較困難）子問(wèn)題解合并得到原問(wèn)題解的過(guò)程：合并排序需要調(diào)用Merge 函數(shù)來(lái)實(shí)現(xiàn)。（Merge 函數(shù)時(shí)間復(fù)雜度為 O(n)）.快速排序一旦左、右兩個(gè)子序列都已分別排序，整個(gè)序列便自然成為有序序列。（異常簡(jiǎn)單，幾乎無(wú)須額外的工作， 省去了從子問(wèn)題解合并得到原問(wèn)題解的過(guò)程）基本程序（一）兩路合并排序#includeclass Sortab

6、leListpublic:SortableList(int mSize)maxSize=mSize;l=new intmaxSize;n=0;SortableList()delete l;void MergeSort();void Input();void Output();private:int *l;int maxSize;int n;void MergeSort(int left,int right);void Merge(int left,int mid,int right);void SortableList:MergeSort()MergeSort(0,n-1);void Sort

7、ableList:MergeSort(int left,int right)if (leftright)int mid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);void SortableList:Merge(int left,int mid,int right)int *temp=new intright-left+1;int i=left,j=mid+1,k=0;while(i=mid)&(j=right)if (li=lj) tempk+=li+;else tempk+=

8、lj+;while (i=mid) tempk+=li+;while (j=right) tempk+=lj+;for (i=0,k=left;k=right;) lk+=tempi+;void SortableList:Input()for(int i=0;ili;n+;void SortableList:Output()for(int i=0;imaxSize;i+)coutli ;coutendl;void main()SortableList l(10);cout請(qǐng)輸入 10 個(gè)數(shù)： endl;l.Input();l.MergeSort();l.Output();（二）快速排序#inc

9、ludeclass SortableListpublic:SortableList(int mSize)maxSize=mSize;l=new intmaxSize;n=0;SortableList()delete l;void QuickSort();void Input();void Output();private:int *l;int maxSize;int n;void S i,int j);void QuickSort(int left,int right);int Partition(int left,int right);void SortableList:S i,int j)

10、int c=li;li=lj;lj=c;int SortableList:Partition(int left,int right)int i=left,j=right+1;dodo i+; while (lilleft);if (ij) S);while (ij);S);return j;void SortableList:QuickSort()QuickSort(0,n-1);void SortableList:QuickSort(int left,int right)if (leftright)int j=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);void SortableList:Input()for(int i=0;ili;n+;void SortableList:Output()for(int i=0;imax