歸并排序算法的原理及JAVA實現

1、歸并排序是利用遞歸和分而治之的技術將數據序列劃分成為越來越小的半子表， 再對半子表排序，最后再用遞歸步驟將排好序的半子表合并成為越來越大的有序 序列，歸并排序包括兩個步驟，分別為：1）劃分子表2）合并半子表首先我們來討論歸并算法，歸并算法將一系列數據放到一個向量中，索引范 圍為first,last,這個序列由兩個排好序的子表構成， 以索引終點（mid）為分界線，以下面一個序列為例7，10，19，25，12，17，21，30，48這樣的一個序列中，分為兩個子序列7,10,19,25 和12,17,21,30,48 ，如 下圖所示：再使用歸并算法的時候的步驟如下：第一步：比較vindexA=7 和

2、vindexB=12,將較小的vindexA取出來放 到臨時向量tempArray中，然后indexA加1第二步：比較vindexA=10 和vindexB=12,將較小的10放到臨時變量 tempArray 中，然后 indexA+;第三步：比較vindexA=19 與vindexB=12，將較小的12存放到臨時變 量 tempArray 中，然后 indexB+;第四步到第七步：按照以上規(guī)則，進行比對和 存儲，得到如下結果:的歸并排序Java實現代碼:package com.sort.merge;public class Merge /*分治法，自頂向下，遞歸分割數組，最終歸并 */pub

3、lic static void merge(int arr,int start,int end) if(starte nd)int mid = (start+end)/2;merge(arr,start,mid);/ 遞歸地對 arrstart.mid 排序 merge(arr,mid+1,end);/ 遞歸地對 arrmid+1.end 排序 doMerge(arr,start,mid,end);/ 組合，將兩個有序區(qū)合并為一個有序區(qū) / 組合，歸并public static void doMerge(int arr,int start,int mid,int end)int tempInd

4、ex = start;int Index = start;int right = mid + 1;int temp = new intarr.length;/ 兩個子序列比較，小的放入臨時數組 while(start = mid & right = end) if(arrstart = arrright) temptempIndex+ = arrstart+;elsetemptempIndex+ = arrright+;/ 剩下的右邊的元素加入臨時數組 while(start = mid) temptempIndex+ = arrstart+;/ 剩下的右邊的元素加入臨時數組 while(ri

5、ght = end)temptempIndex+ = arrright+;/ 復制臨時數據 temp 中的數據到 arr 數組 while(Index end) arrIndex = tempIndex+;public static void main(String args) / TODO Auto-generated method stubint arr = 2,4,6,8,1,3,5,9; merge(arr,0,arr.length-1);for (int i = 0; i arr.length; i+) System.out.print(arri); 采用分治法進行自頂向下的算法設計

6、，形式更為簡潔。 (1)分治法的三個步驟設歸并排序的當前區(qū)間是 Rlow.high ，分治法的三個步驟是：分解：將當前區(qū)間一分為二，即求分裂點求解：遞歸地對兩個子區(qū)間Rlow.mid和Rmid+1.high進行歸并排序；組合：將已排序的兩個子區(qū)間Rlow.mid和Rmid+1.high歸并為一個 有序的區(qū)間 Rlow.high 。遞歸的終結條件：子區(qū)間長度為 1（一個記錄自然有序）。（2）具體算法void MergeSortDC（SeqList R ， int low ， int high）/ 用分治法對 Rlow.high 進行二路歸并排序int mid ；if（lowhigh）/ 區(qū)間長度大于 1mid=（low+high）/2 ； / 分解MergeSortDC（R， low， mid）; / 遞歸地對 Rlow.mid 排序MergeSortD