熱心網友

歸并排序 可以運用分而治之方法來解決排序問題，該問題是將n 個元素排成非遞減順序。分而治之方法通常用以下的步驟來進行排序算法：若n 為1，算法終止；否則，將這一元素集合分割成兩個或更多個子集合，對每一個子集合分別排序，然后將排好序的子集合歸并為一個集合。 假設僅將n 個元素的集合分成兩個子集合。現在需要確定如何進行子集合的劃分。一種可能性就是把前面n- 1個元素放到第一個子集中（稱為A），最后一個元素放到第二個子集里（稱為B）。按照這種方式對A遞歸地進行排序。由于B僅含一個元素，所以它已經排序完畢，在A排完序后，只需要用程序2 - 1 0中的函數i n s e r t將A和B合并起來。把這種排序算法與I n s e r t i o n S o r t（見程序2 - 1 5）進行比較，可以發現這種排序算法實際上就是插入排序的遞歸算法。該算法的復雜性為O (n 2 )。把n 個元素劃分成兩個子集合的另一種方法是將含有最大值的元素放入B，剩下的放入A中。然后A被遞歸排序。為了合并排序后的A和B，只需要將B添加到A中即可。假如用函數M a x（見程序1 - 3 1）來找出最大元素，這種排序算法實際上就是S e l e c t i o n S o r t（見程序2 - 7）的遞歸算法。 假如用冒泡過程（見程序2 - 8）來尋找最大元素并把它移到最右邊的位置，這種排序算法就是B u b b l e S o r t（見程序2 - 9）的遞歸算法。這兩種遞歸排序算法的復雜性均為(n2 )。若一旦發現A已經被排好序就終止對A進行遞歸分割，則算法的復雜性為O(n2 )（見例2 - 1 6和2 - 1 7）。 上述分割方案將n 個元素分成兩個極不平衡的集合A和B。A有n- 1個元素，而B僅含一個元素。下面來看一看采用平衡分割法會發生什么情況： A集合中含有n/k 個元素，B中包含其余的元素。遞歸地使用分而治之方法對A和B進行排序。然后采用一個被稱之為歸并（ m e rg e）的過程，將已排好序的A和B合并成一個集合。 例2-5 考慮8個元素，值分別為[ 1 0，4，6，3，8，2，5，7 ]。如果選定k = 2，則[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]將被分別獨立地排序。結果分別為[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。從兩個序列的頭部開始歸并這兩個已排序的序列。元素2比3更小，被移到結果序列；3與5進行比較，3被移入結果序列；4與5比較，4被放入結果序列；5和6比較，。。如果選擇k= 4，則序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]將被排序。排序結果分別為[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6&n。