程序設(shè)計綜合實(shí)踐-歸并排序和快速排序

三、歸并排序

前面討論的幾種簡單排序方法，算法比較簡單，時間復(fù)雜度都是，適用于問題規(guī)模不太大的情況。它們都是穩(wěn)定的排序方法，即：可以保證，兩個關(guān)鍵字相同的元素，原序列中排在前面元素，結(jié)果序列中也排在前面，保持相對次序不變。歸并排序同樣應(yīng)用了分治法。當(dāng)問題規(guī)模較小，待排序序列長度不超過1時，無需排序；當(dāng)問題規(guī)模較大時，將較大規(guī)模待排序的序列一分為二，先后分別對前后兩段問題規(guī)模減半子序列使用歸并排序進(jìn)行排序，并將排序完成后前后兩段子序列歸并成一段有序序列，歸并后的有序序列存放在輔助數(shù)組中，最后，將輔助數(shù)組中有序序列拷貝至原數(shù)組空間。排序遞歸進(jìn)行，最終劃分后的子序列長度為1。1

2圖3.1歸并排序示意圖//算法3.5歸并排序。對存放n個元素的數(shù)組按關(guān)鍵字遞增排序voidMergeSort(ElemTypeA[],intlow,inthigh,ElemTypeAux[]){if(low>=high)return;//規(guī)模不超過1，無需排序m=(low+high)div2;//二分法劃分MergeSort(A,low,m，Aux);//前一半子序列排序MergeSort(A,m+1,high，Aux);//后一半子序列排序Merge(A,low,m,high,Aux);//歸并兩段有序子序列for(i=low;i<=high;++i)A[i]=Aux[i];//移動回原數(shù)組}3

//歸并排序中有序段合并子算法voidMerge(ElemTypeA[],intlow,intm,inthigh,ElemTypeAux[]){i=low;//前段有序子序列起點(diǎn)j=m+1;//后段有序子序列起點(diǎn)k=i;//歸并結(jié)果起始下標(biāo)while(i<=m&&j<=high){//較小元素先轉(zhuǎn)移至結(jié)果緩沖區(qū)if(A[i].key<=A[j].key)Aux[k++]=A[i++];elseAux[k++]=A[j++];}

4while(i<=m)//前段剩余元素轉(zhuǎn)移至結(jié)果緩沖區(qū)Aux[k++]=A[i++];while(j<=high)//后段剩余元素轉(zhuǎn)移至結(jié)果緩沖區(qū)Aux[k++]=A[j++];}5歸并排序的主要操作是元素比較和元素移動，元素移動包括歸并時移動到輔助數(shù)組和輔助數(shù)組移動回原數(shù)組，元素移動次數(shù)多于元素比較次數(shù)，所以，我們下面考慮算法時間復(fù)雜度時只需考慮元素移動次數(shù)。假設(shè)T(n)是n個元素歸并排序的時間復(fù)雜度，N是大于等于n且符合N=2k的最小正整數(shù)，k為正整數(shù)，k=log2N，N<2n。N個元素的歸并排序包括2個N/2子序列的歸并排序和2N次元素的移動：T(N)=2T(N/2)+2N繼續(xù)展開，可得：顯然，T(N)是nlog2n數(shù)量級的，T(n)也一樣。任何情況下，歸并排序的時間復(fù)雜度都是O(nlog2n)。另外，歸并排序需要使用與原數(shù)組空間相同大小的輔助數(shù)組空間，空間復(fù)雜度是O(n)。6四、快速排序

快速排序同樣使用了分治法。當(dāng)問題規(guī)模較小，待排序序列長度不超過1時，無需排序；當(dāng)問題規(guī)模較大時，快速排序先將較大規(guī)模待排序的序列劃分為三個部分：中間部分只有一個元素，稱為樞軸元素，前面部分所有元素小于等于樞軸元素，后面部分所有元素大于等于樞軸元素；這樣，只要分別對前面部分元素子序列和后面部分元素子序列完成排序即可，前后兩部分問題規(guī)模大幅減小后子序列的排序同樣可以使用快速排序進(jìn)行。7

8圖3.2a快速排序示意圖//算法3.6a快速排序遞歸部分。對存放n個元素的數(shù)組按關(guān)鍵字遞增排序voidQuickSort(ElemTypeA[],intlow,inthigh){if(low>=high)return;//規(guī)模不超過1的子序列無需排序pivot=QuickPass(A,low,high);//快速劃分，返回劃分后樞軸元素所在位置QuickSort(A,low,pivot-1);//對前一段子序列快速排序QuickSort(A,pivot+1,high);//對后一段子序列快速排序}9

10圖3.2b快速排序中快速劃分示意圖//算法3.6b快速排序劃分部分。intQuickPass(ElemTypeA[],intlow,inthigh){ElemTypex=A[low];//樞軸元素while(low<high){while(low<high&&x.key<=A[high].key)--high;//從右往左掃描，保留右邊大于等于樞軸元素的所有元素位置不變if(low==high)break;A[low++]=A[high];//較小元素從右邊移至左邊空余位置

11while(low<high&&x.key>=A[low].key)++low;//從左往右掃描，保留左邊小于等于樞軸元素的所有元素位置不變if(low==high)break;A[high--]=A[low];//較大元素從左邊移至右邊空余位置}A[low]=x;//樞軸元素放回空余位置returnlow;//返回樞軸元素所在位置}

12快速排序的時間復(fù)雜度?？焖倥判虻闹饕僮鳛樵乇容^和元素移動，元素移動次數(shù)不多于元素比較次數(shù)，下面考慮算法時間復(fù)雜度時只考慮元素比較次數(shù)。假設(shè)T(n)為n個元素快速排序時平均時間復(fù)雜度，T(0)=0，T(1)=0，N>1時，Pi為劃分時有i個元素位于樞軸元素左邊段的概率，n個元素劃分一次的比較次數(shù)為n-1，得到：不失一般性，假設(shè)所有Pi相等，Pi=1/n，即：

展開，得到：

13

14消除分母后兩邊相減，得到：nT(n)-(n-1)T(n-1)=2(n-1)+2T(n-1)化簡后，等價于：nT(n)-(n+1)T(n-1)=2(n-1)等價于：

繼續(xù)展開后累加求和，得到：從右側(cè)圖示中柱形面積小于等于對應(yīng)積分，可以看到下述公式：展開后化簡得到：因此：