實驗報告（2015/2016學年第二學期）課程名稱實驗名稱 分治法實現快速排序與兩路合并排序實驗時間 年 月 日指導單位 十算機科學與技術系指導教師學生姓名 班級學號學院（系） 專業實驗報告

實驗名稱分治法指導教師實驗類型驗證 實驗學時 2實驗時間一、實驗目的和要求實驗目的：理解分治法的算法思想，閱讀實現書上已有的部分程序代碼并完善程序，加深對分治法的算法原理及實現過程的理解。實驗要求：用分治法實現一組無序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，編程實現分別用這兩種方法將輸入的一組無序序列排序為有序序列后輸出。二、實驗環境（實驗設備）硬件：微型計算機軟件：Windows操作系統、MicrosoftVisualC++6.0三、實驗原理及內容實驗原理：分治法：即分而治之。將問題分解為規模較小，相互獨立，類型相同的問題進行求解。對于無序數組的有序排序也就是按某種方式將序列分成兩個或多個子序列，分別進行排序，再將已排序的子序列合并成一個有序序列。實驗內容：兩路合并排序算法的基本思想是：將待排序元素序列一分為二，得到兩個長度基本相等的子序列，其過程類似于對半搜索；然后將子序列分別排序，如果子序列較長,還可以繼續細分，知道子序列長度不超過1為止。以上的實現由下列代碼執行：voidSortableList::MergeSort(){MergeSort(0,n-1);}voidSortableList::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}函數MergeSort是類SortableList上的公有成員函數。mid=(left+right)/2;將函數劃分為兩個長度基本相等的子序列，用遞歸來執行兩個子序列的內部排序。而Merge函數是將有序的子序列合并，通過合并過程將自問題的解組合成元問題的解。通過比較兩個序列中的最小者，輸出其中的較小者，重復此過程，直到一個序列為空，如果還有元素為輸出則輸出即可。其中對于Merge函數代碼如下：voidSortableList::Merge(intleft,intmid,intright)//將兩個長度之和為n的有序子序列合并一個有序序列{int*temp=newint[right-left+1];inti=left,j二mid+1,k=0;while((i〈二mid)&&(j<=right))if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++];for(i=0,k=left;k<=right;)l[k++]二temp[i++];}快速排序算法的基本思想是：在待排序序列K[left:right]上選擇一個基準元素(通常是最左邊的元素)，通過一趟分劃操作將序列分成左右兩個子序列，左子序列中所有元素都小于等于該基準元素，有子序列中所有元素都大于等于該基準元素。劃分操作如下：intSortableList::Partition(intleft,intright){inti=left,j二right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j);Swap(left,j);returnj;}則當前基準元素所在的位置位于左、右子序列的中間，即是其排序完成后的最終位置。通過遞歸調用，對左子序列和右子序列再分別進行快速排序算法的調用。由于每一趟分劃結束后，左子序列中的元素均不大于基準元素，右子序列中的元素均不小于基準元素。而每次分劃后，對分劃得到的左、右子序列的快速排序又均是就地進行,所以一旦左、右兩個子序列都已分別排好序后，無需再執行任何計算，整個序列就是所要求的有序序列了。因此類中應定義成員函數QuickSort來完成遞歸快速排序算法的調用和成員函數?？焖倥判虿僮魅缦拢簐oidSortableList::QuickSort(){QuickSort(0,n-l);}voidSortableList::QuickSort(intleft,intright){if(left<right){intj二Partition(left,right);QuickSort(left,j-l);QuickSort(j+1,right);}}比較合并排序和快速排序的異同。合并排序一一將序列一分為二即可?？焖倥判颉枵{用Partition函數將一個序列劃分為子序列。子問題解合并得到原問題解的過程：合并排序一一需要調用Merge函數來實現。(Merge函數時間復雜度為O(n))..快速排序一一一旦左、右兩個子序列都已分別排序，整個序列便自然成為有序序列。程序中的其他函數：輸入輸出函數：voidSortableList::Input(){for(inti=O;i<maxSize;i++){cin>>l[i];n++;}}voidSortableList::0utput(){for(inti=O;i<maxSize;i++){cout<<l[i]<<"";}}主函數：voidmain(){intn;inti;cout<<"***************************************"<<endl<<endl;cout<<" 1兩路合并排序"<<" "<<"2快速排序"<<endl<<endl;cout<<"***************************************"<<endl<<endl;while(l){cout<<"************請選擇排序方式*************"<<endl;cin>>i;if(i!=l&&i!=2){cout<<"fault"<<endl;break;}cout<<"***********請輸入比較個數************"<<endl;cin>>n;SortableListl(n);cout<<"************請輸入"<<n<〈"個數：*************"<<endl;l.Input();if(i=1)l.MergeSort();elsel.QuickSort();cout<<"************排序后序列是：***********"<<endl;l.0utput();cout<<endl;}}實驗結果：實驗用例(1)722657884280724860(2)00000

完整實驗代碼：#include<iostream.h>classSortableList{public:SortableList(intmSize)//構造函數{maxSize二mSize;l二newint[maxSize];n=0;}~SortableList()//析構函數{delete[]l;}voidMergeSort();voidQuickSort();voidInput();voidOutput();private:int*l;intmaxSize;intn;voidMergeSort(intleft,intright);voidMerge(intleft,intmid,intright);voidSwap(inti,intj);voidQuickSort(intleft,intright);intPartition(intleft,intright);};voidSortableList::Swap(inti,intj){intc=l[i];l[i]=l[j];l[j]=c;}intSortableList::Partition(intleft,intright){inti=left,j二right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j);Swap(left,j);returnj;}voidSortableList::QuickSort(){QuickSort(0,n-l);}voidSortableList::QuickSort(intleft,intright){if(left<right){intj=Partition(left,right);QuickSort(left,j-l);QuickSort(j+1,right);}}voidSortableList::MergeSort(){MergeSort(0,n-l);}voidSortableList::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}voidSortableList::Merge(intleft,intmid,intright)//將兩個長度之和為n的有序子序列合并一個有序序列{int*temp=newint[right-left+1];inti=left,j二mid+l,k=0;while((i<=mid)&&(j〈二right))if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++];for(i=0,k=left;k〈二right;)l[k++]二temp[i++];}voidSortableList::Input(){for(inti=O;i<maxSize;i++){cin>>l[i];n++;}}voidSortableList::0utput(){for(inti=O;i<maxSize;i++){cout<<l[i]<<"";}}voidmain(){intn;inti;cout<<"***************************************"<<endl<<endl;cout<<" 1兩路合并排序"<<" "<<"2快速排序"<<endl<<endl;cout<<"***************************************"<<endl<<endl;while(l){cout<<"************請選擇排序方式*************"<<endl;cin>>i;if(i!=l&&i!=2){cout<<"fault"<<endl;break;}cout<<"***********請輸入比較個數************"<<endl;cin>>n;SortableListl(n);cout<<"******