歸并排序是利用遞歸和分而治之的技術將數據序列劃分成為越來越小的半子表，再對半子表排序，最后再用遞歸步驟將排好序的半子表合并成為越來越大的有序序列，歸并排序包括兩個步驟，分別為：

1）劃分子表

2）合并半子表

首先我們來討論歸并算法，歸并算法將一系列數據放到一個向量中，索引范圍為[first,last],這個序列由兩個排好序的子表構成，以索引終點（mid）為分界線，以下面一個序列為例

7，10，19，25，12，17，21，30，48

這樣的一個序列中，分為兩個子序列 7,10,19,25  和 12,17,21,30,48，如下圖所示：

再使用歸并算法的時候的步驟如下：

第一步：比較v[indexA]=7和v[indexB]=12,將較小的v[indexA]取出來放到臨時向量tempArray中，然后indexA加1

第二步：比較v[indexA]=10和v[indexB]=12,將較小的10放到臨時變量tempArray中，然后indexA++;

第三步：比較v[indexA]=19與v[indexB]=12，將較小的12存放到臨時變量tempArray中，然后indexB++;

第四步到第七步：按照以上規則，進行比對和存儲，得到如下結果：

最后一步：將子表b中剩余項添加到臨時向量tempArray中

然后將臨時變量中的值按照索引位置，拷貝回向量v中，就完成了對向量v的歸并排序

算法函數為：

public void Merger(int[] v, int first, int mid, int last){ Queue<int> tempV = new Queue<int>(); int indexA, indexB; //設置indexA，并掃描subArray1 [first,mid] //設置indexB,并掃描subArray2 [mid,last] indexA = first; indexB = mid; //在沒有比較完兩個子標的情況下，比較 v[indexA]和v[indexB] //將其中小的放到臨時變量tempV中 while (indexA < mid && indexB < last) { if (v[indexA] < v[indexB]) {  tempV.Enqueue(v[indexA]);  indexA++; } else {  tempV.Enqueue(v[indexB]);  indexB++; } } //復制沒有比較完子表中的元素 while (indexA < mid) { tempV.Enqueue(v[indexA]); indexA++; } while (indexB < last) { tempV.Enqueue(v[indexB]); indexB++; } int index = 0; while (tempV.Count > 0) { v[first+index] = tempV.Dequeue(); index++; }}

實現歸并排序；歸并排序算法分為兩步，第一步：先將原來的數據表分成排好序的子表，然后調用 Merger  對子表進行歸并，使之成為有序表，例如有如下向量：

25，10，7，19，3，48，12，17，56，30，21

對此序列進行歸并排序的步驟為：

歸并算法函數為

public void MergerSort(int[] v, int first, int last){ if (first + 1 < last) { int mid = (first + last) / 2; MergerSort(v, first, mid); MergerSort(v, mid, last); Merger(v, first, mid, last); }}

歸并算法的劃分子表和歸并子表與原數據序列次序無關，因此算法的最壞情況，最壞情況和平均情況時間復雜度是一樣的

下面是歸并算法的函數調用圖

示例程序：http://xiazai.VeVB.COm/201606/yuanma/MergerSort(VeVB.COm).rar

以上就是本文的全部內容，希望能給大家一個參考，也希望大家多多支持武林網。