歸并排序算法的原理及JAVA實(shí)現(xiàn)

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

2、vindexB=12,將較小的vindexA取出來放 到臨時(shí)向量tempArray中，然后indexA加1第二步：比較vindexA=10 和vindexB=12,將較小的10放到臨時(shí)變量 tempArray 中，然后 indexA+;第三步：比較vindexA=19 與vindexB=12，將較小的12存放到臨時(shí)變 量 tempArray 中，然后 indexB+;第四步到第七步：按照以上規(guī)則，進(jìn)行比對和 存儲(chǔ)，得到如下結(jié)果:的歸并排序Java實(shí)現(xiàn)代碼:package com.sort.merge;public class Merge /*分治法，自頂向下，遞歸分割數(shù)組，最終歸并 */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);/ 組合，將兩個(gè)有序區(qū)合并為一個(gè)有序區(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;/ 兩個(gè)子序列比較，小的放入臨時(shí)數(shù)組 while(start = mid & right = end) if(arrstart = arrright) temptempIndex+ = arrstart+;elsetemptempIndex+ = arrright+;/ 剩下的右邊的元素加入臨時(shí)數(shù)組 while(start = mid) temptempIndex+ = arrstart+;/ 剩下的右邊的元素加入臨時(shí)數(shù)組 while(ri

5、ght = end)temptempIndex+ = arrright+;/ 復(fù)制臨時(shí)數(shù)據(jù) temp 中的數(shù)據(jù)到 arr 數(shù)組 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); 采用分治法進(jìn)行自頂向下的算法設(shè)計(jì)

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