分治法實現(xiàn)一組無序序列的兩路合并排序和快速排序(共10頁)

1、精選優(yōu)質文檔-傾情為你奉上實 驗 報 告（2011/2012學年 第一學期）課程名稱算法分析與設計A實驗名稱分治策略實驗時間年月日指導單位計算機學院軟件工程系指導教師學生姓名班級學號學院(系)專 業(yè)專心-專注-專業(yè)實 驗 報 告實驗名稱分治策略指導教師實驗類型驗證實驗學時2實驗時間一、 實驗目的和任務理解分治法的算法思想，閱讀實現(xiàn)書上已有的部分程序代碼并完善程序，加深對分治法的算法原理及實現(xiàn)過程的理解。 用分治法實現(xiàn)一組無序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，編程實現(xiàn)分別用這兩種方法將輸入的一組無序序列排序為有序序列后輸出。 二、 實驗環(huán)境(實驗設備) VC+6

2、.0三、實驗原理及內容（包括操作過程、結果分析等）實驗原理1、排序是數(shù)據(jù)處理中常用的重要手段，是指將一個元素序列調整為按指定關鍵字值的遞增（或遞減）次序排列的有序序列。用分治法求解排序問題的思路是，按某種方式將序列分成兩個或多個子序列，分別進行排序，再將已排序的子序列合并成一個有序序列。合并排序和快速排序是兩種典型的符合分治策略的排序算法。 2、如果采用順序存儲的可排序表作為算法實現(xiàn)的數(shù)據(jù)結構，則需要定義一個可排序表類SortableList，兩路合并算法和快速排序算法均由定義在該類上的函數(shù)實現(xiàn)。其中 Input函數(shù)和 Output函數(shù)分別用于向可排序表中輸入待排序序列，以及輸出已經排序好的序

3、列。3、兩路合并排序算法的基本思想是：將待排序元素平分成大小大致相同的兩個子序列，然后對每個子序列分別使用遞歸的方法進行兩路合并排序，直到子序列長度變?yōu)?，最后利用合并算法將得到的已排序好的兩個子序列合并成一個有序的序列。 兩路合并排序算法的核心部分是將子問題的解組合成原問題解得合并操作。常用的操作是新建一個序列，序列的大小等于要合并的兩個子序列的長度之和。比較兩個子序列中的最小值，輸出其中較小者到新建的序列中，重復此過程直到其中一個子序列為空。如果另一個子序列中還有元素未輸出，則將剩余元素依次輸出到新建序列中即可。最終得到一個有序序列。 4、結合書上已有的程序代碼，使用分治法的快速排序算法，

4、實現(xiàn)對初始序列的排序。快速排序算法的基本思想是：（1）在待排序序列 Kleft:right上選擇一個基準元素（通常是最左邊的元素 Kleft），通過一趟分劃操作將序列分成左右兩個子序列，左子序列中所有元素都小于等于該基準元素，有子序列中所有元素都大于等于該基準元素。則當前基準元素所在的位置位于左、右子序列的中間，即是其排序完成后的最終位置。（2）通過遞歸調用，對左子序列和右子序列再分別進行快速排序算法的調用。（3）由于每一趟分劃結束后，左子序列中的元素均不大于基準元素，右子序列中的元素均不小于基準元素。而每次分劃后，對分劃得到的左、右子序列的快速排序又均是就地進行，所以一旦左、右兩個子序列都已

5、分別排好序后，無需再執(zhí)行任何計算，整個序列就是所要求的有序序列了。因此類中應定義成員函數(shù) QuickSort來完成遞歸快速排序算法的調用和成員函數(shù)5、比較合并排序和兩種算法的異同。 問題分解過程： 合并排序將序列一分為二即可。 （十分簡單） 快速排序需調用 Partition函數(shù)將一個序列劃分為子序列。（分解方法相對較困難）子問題解合并得到原問題解的過程：合并排序需要調用 Merge函數(shù)來實現(xiàn)。（Merge函數(shù)時間復雜度為O(n)）.快速排序一旦左、右兩個子序列都已分別排序，整個序列便自然成為有序序列。（異常簡單，幾乎無須額外的工作，省去了從子問題解合并得到原問題解的過程） 基本程序（一） 兩

6、路合并排序#include<iostream.h> class SortableList public: 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 ri

7、ght); void SortableList:MergeSort() MergeSort(0,n-1); void SortableList:MergeSort(int left,int right) if (left<right) 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

8、i=left,j=mid+1,k=0; while(i<=mid)&&(j<=right) if (li<=lj) tempk+=li+; else tempk+=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;i<maxSize;i+) cin>>li; n+; void SortableList:O

9、utput() for(int i=0;i<maxSize;i+) cout<<li<<" " cout<<endl; void main() SortableList l(10); cout<<"請輸入10個數(shù)："<<endl; l.Input(); l.MergeSort(); l.Output();（二）快速排序#include<iostream.h>class SortableListpublic: SortableList(int mSize) maxSize=mSi

10、ze; l=new intmaxSize; n=0; SortableList() delete l; void QuickSort(); void Input(); void Output();private: int *l; int maxSize; int n;void Swap(int i,int j); void QuickSort(int left,int right);int Partition(int left,int right);void SortableList:Swap(int i,int j)int c=li;li=lj;lj=c;int SortableList:P

11、artition(int left,int right)int i=left,j=right+1;dodo i+; while (li<lleft);do j-; while (lj>lleft);if (i<j) Swap(i,j);while (i<j);Swap(left,j);return j;void SortableList:QuickSort()QuickSort(0,n-1);void SortableList:QuickSort(int left,int right)if (left<right)int j=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);void SortableList:Input() for(int i=0;i<maxSize;i+) cin>>li; n+; void SortableList:Output() for(int i=0;i<maxSize;i+) cout<<li<<" " cout&