實(shí)驗(yàn)報(bào)告-歸并快速排序

《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告一學(xué)號(hào)：1004091130姓名：金玉琦日期：2011-10-13得分：一、實(shí)驗(yàn)內(nèi)容：歸并排序與快速排序。二、所用算法的根本思想及復(fù)雜度分析：1.分治法分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題，劃分成一些規(guī)模較小的問題，以便各個(gè)擊破，分而治之。2.歸并排序1〕根本思想歸并排序其分治策略如下：劃分：將待排序的序列從n/2處劃分為兩個(gè)長度相等的序列。求解子問題：分別對(duì)這兩個(gè)子序列進(jìn)行歸并排序，得到兩個(gè)有序子序列。合并：將這兩個(gè)有序子序列合并成一個(gè)有序序列。2〕復(fù)雜度分析二路歸并排序的合并步的時(shí)間復(fù)雜度為O(n)，所以，二路歸并排序算法存在如下遞推式： 1 n=2T(n)= 2T(n/2)+n n>2將上式進(jìn)行迭代運(yùn)算，計(jì)算的二路歸并排序的時(shí)間代價(jià)是O(nlogn)。二路歸并排序歸并過程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，因此其空間復(fù)雜度為O(n)。3.快速排序1〕根本思想快速排序的分治思想如下：劃分：選定一個(gè)記錄作為軸值，以軸值為基準(zhǔn)將整個(gè)序列劃分成兩個(gè)子序列，軸值的位置i在劃分過程中確定，并且前一個(gè)子序列中的記錄的值均小于或等于軸值，后一個(gè)子序列的記錄的值均大于或等于軸值。求解子問題：分別對(duì)劃分后的每一個(gè)子序列遞歸處理。合并：將軸值前后的子序列的排序是就地進(jìn)行的，所以合并不需要執(zhí)行任何操作。2〕復(fù)雜度分析在最好的情況下每次劃分對(duì)一個(gè)記錄定位后，該記錄的左右兩側(cè)子序列的長度相同。在具有n個(gè)記錄的序列中，一次劃分需要對(duì)整個(gè)帶排序的序列掃描一遍，所需時(shí)間為O(n)。設(shè)T(n)是對(duì)n個(gè)記錄的序列進(jìn)行排序的時(shí)間，每次劃分后，正好把帶劃分的區(qū)間劃分為長度相同的兩個(gè)子序列，那么有：T(n)≤2T(n/2)+n≤2(2T(n/4)+n/2)+n=4T(n/4)+2n≤4(2T(n/8)+n/4)+2n=8T(n/8)+3n……≤nT(1)+nlogn=O(nlogn)因此時(shí)間復(fù)雜度是O(nlogn)。在最壞的情況下，待排序的記錄為正序或逆序時(shí)，時(shí)間復(fù)雜度為O(n)。由于快速排序是遞歸執(zhí)行，需要一個(gè)棧存放每一層遞歸調(diào)用的必要信息，其最大的容量應(yīng)該與遞歸調(diào)用的深度一致。最好情況因?yàn)橐M(jìn)行l(wèi)ogn次遞歸調(diào)用，棧的深度是O(logn)；最壞的情況下，進(jìn)行n-1次調(diào)用，所以棧的深度為O(n)。三、源程序及注釋：1、歸并排序voidMergeSort(intr[],intrl[],ints,intt){ intm; if(s==t) rl[s]=r[s]; else { m=(s+t)/2; MergeSort(r,rl,s,m); //歸并排序前半個(gè)子序列 MergeSort(r,rl,m+1,t); //歸并排序后半個(gè)子序列 Merge(rl,r,s,m,t); //合并兩個(gè)已排序的子序列 }}2、合并有序子序列voidMerge(intr[],intrl[],ints,intm,intt){ inti=s; intj=m+1; intk=s; while(i<=m&&j<=t) { if(r[i]<=r[j]) rl[k++]=r[i++]; //取r[i]和r[j]中較小的放入rl[k]中 else rl[k++]=r[j++]; } if(i<=m) { while(i<=m) rl[k++]=r[i++];//假設(shè)第一個(gè)子序列沒有處理完，進(jìn)行收尾處理 } else { while(j<=t) rl[k++]=r[j++];//假設(shè)第二個(gè)子序列沒有處理完，進(jìn)行收尾處理 } for(intn=s;n<=t;n++) { r[n]=rl[n]; //將合并完成后的rl[]序列送回r[]序列中 }}3、快速排序voidQuickSort(intr[],intfirst,intend){ intpivot; if(first<end) { pivot=Partition(r,first,end); //pivot是軸值在序列中位置 QuickSort(r,first,pivot-1); //遞歸左側(cè)序列進(jìn)行快排 QuickSort(r,pivot+1,end); //遞歸右側(cè)序列進(jìn)行快排 }}快速排序的一次劃分intPartition(intr[],intfirst,intend){ inti=first; intj=end; //初始化 inttemp=0; 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[i]; r[i]=r[j]; r[j]=temp; //將較小的記錄交換到后面 j--; } } returni; //返回軸值的最終位置}四、運(yùn)行輸出結(jié)果：五、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題、采取的措施及獲得的相關(guān)經(jīng)驗(yàn)教訓(xùn)：調(diào)試過程中