java歸并排序

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過(guò)程中需要訪問(wèn)外存。常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是歸并排序算法：

你所需要的網(wǎng)站建設(shè)服務(wù)，我們均能行業(yè)靠前的水平為你提供.標(biāo)準(zhǔn)是產(chǎn)品質(zhì)量的保證，主要從事成都做網(wǎng)站、成都網(wǎng)站制作、企業(yè)網(wǎng)站建設(shè)、成都手機(jī)網(wǎng)站制作、網(wǎng)頁(yè)設(shè)計(jì)、品牌網(wǎng)站制作、網(wǎng)頁(yè)制作、做網(wǎng)站、建網(wǎng)站。創(chuàng)新互聯(lián)擁有實(shí)力堅(jiān)強(qiáng)的技術(shù)研發(fā)團(tuán)隊(duì)及素養(yǎng)的視覺(jué)設(shè)計(jì)專(zhuān)才。

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫(xiě)，所以就有了第 2 種方法）； 自下而上的迭代；

在《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對(duì)于遞歸法，作者卻認(rèn)為：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中這種方式不太可行，因?yàn)檫@個(gè)算法的遞歸深度對(duì)它來(lái)講太深了。

說(shuō)實(shí)話，我不太理解這句話。意思是 JavaScript 編譯器內(nèi)存太小，遞歸太深容易造成內(nèi)存溢出嗎？還望有大神能夠指教。

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是 O(nlogn) 的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。

2. 算法步驟

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；

設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；

比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；

重復(fù)步驟 3 直到某一指針達(dá)到序列尾；

將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

3. 動(dòng)圖演示

代碼實(shí)現(xiàn) JavaScript 實(shí)例 function mergeSort ( arr ) { ? // 采用自上而下的遞歸方法

var len = arr. length ;

if ( len

JAVA歸并排序算法，有兩行代碼看不懂

以var a = [4,2,6,3,1,9,5,7,8,0];為例子。

1.希爾排序。 希爾排序是在插入排序上面做的升級(jí)。是先跟距離較遠(yuǎn)的進(jìn)行比較的一些方法。

function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap0){ for (var k = 0; k gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i = k+gap; i len; i=i+gap) { temp = arr[i]; tagArr.push(temp); for (j=i-gap; j -1; j=j-gap) { if(arr[j]temp){ arr[j+gap] = arr[j]; }else{ break; } } arr[j+gap] = temp; } console.log(tagArr,"gap:"+gap);//輸出當(dāng)前進(jìn)行插入排序的數(shù)組。 console.log(arr);//輸出此輪排序后的數(shù)組。 } gap = parseInt(gap/2); } return arr; }

過(guò)程輸出：

[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

由輸出可以看到。第一輪間隔為5。依次對(duì)這些間隔的數(shù)組插入排序。

間隔為5：

[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

間隔為2：

[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 4 6 0 5 8 2 3 9 7 1

排序后：

[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]

間隔為1：

排序后：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。

2.快速排序。把一個(gè)數(shù)組以數(shù)組中的某個(gè)值為標(biāo)記。比這個(gè)值小的放到數(shù)組的左邊，比這個(gè)值得大的放到數(shù)組的右邊。然后再遞歸 對(duì)左邊和右邊的數(shù)組進(jìn)行同樣的操作。直到排序完成。通常以數(shù)組的第一個(gè)值為標(biāo)記。

代碼:

function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tag; if(len2){ return arr; } tag = arr[0]; for(i=1;ilen;i++){ if(arr[i]=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]); } } return quickSort(leftArr).concat(tag,quickSort(rightArr)); }

3.歸并排序。把一系列排好序的子序列合并成一個(gè)大的完整有序序列。從最小的單位開(kāi)始合并。然后再逐步合并合并好的有序數(shù)組。最終實(shí)現(xiàn)歸并排序。

合并兩個(gè)有序數(shù)組的方法：

function subSort(arr1,arr2){ var len1 = arr1.length,len2 = arr2.length,i=0,j=0,arr3=[],bArr1 = arr1.slice(),bArr2 = arr2.slice(); while(bArr1.length!=0 || bArr2.length!=0){ if(bArr1.length == 0){ arr3 = arr3.concat(bArr2); bArr2.length = 0; }else if(bArr2.length == 0){ arr3 = arr3.concat(bArr1); bArr1.length = 0; }else{ if(bArr1[0]=bArr2[0]){ arr3.push(bArr1[0]); bArr1.shift(); }else{ arr3.push(bArr2[0]); bArr2.shift(); } } } return arr3; }

歸并排序：

function mergeSort(arr){ var len= arr.length,arrleft=[],arrright =[],gap=1,maxgap=len-1,gapArr=[],glen,n; while(gapmaxgap){ gap = Math.pow(2,n); if(gap=maxgap){ gapArr.push(gap); } n++; } glen = gapArr.length; for (var i = 0; i glen; i++) { gap = gapArr[i]; for (var j = 0; j len; j=j+gap*2) { arrleft = arr.slice(j, j+gap); arrright = arr.slice(j+gap,j+gap*2); console.log("left:"+arrleft,"right:"+arrright); arr = arr.slice(0,j).concat(subSort(arrleft,arrright),arr.slice(j+gap*2)); } } return arr; }

排序[4,2,6,3,1,9,5,7,8,0]輸出：

left:4 right:2 left:6 right:3 left:1 right:9 left:5 right:7 left:8 right:0 left:2,4 right:3,6 left:1,9 right:5,7 left:0,8 right: left:2,3,4,6 right:1,5,7,9 left:0,8 right: left:1,2,3,4,5,6,7,9 right:0,8

看出來(lái)從最小的單位入手。

第一輪先依次合并相鄰元素：4,2; 6,3; 1,9; 5,7; 8,0

合并完成之后變成： [2,4,3,6,1,9,5,7,0,8]

第二輪以2個(gè)元素為一個(gè)單位進(jìn)行合并：[2,4],[3,6]; [1,9],[5,7]; [0,8],[];

合并完成之后變成：[2,3,4,6,1,5,7,9,0,8]

第三輪以4個(gè)元素為一個(gè)單位進(jìn)行合并：[2,3,4,6],[1,5,7,9]; [0,8],[]

合并完成之后變成： [1,2,3,4,5,6,7,9,0,8];

第四輪以8個(gè)元素為一個(gè)單位進(jìn)行合并： [1,2,3,4,5,6,7,9],[0,8];

合并完成。 [0,1,2,3,4,5,6,7,8,9];

java實(shí)現(xiàn)歸并排序問(wèn)題

public void mySort(int low,int high){

int lo=low;

int hi=high;

if (lo=hi) {

return;

}else{

boolean flag=false;

while (lohi) {

if (arrs[lo]arrs[hi]) {

int temp=arrs[lo];

arrs[lo]=arrs[hi];

arrs[hi]=temp;

flag=!flag;

}else{

if (flag) {

lo++;

}else{

hi--;

}

}

}

lo--;

hi++;

mySort(low,lo);

mySort(hi,high);

}

}

這里是遞歸加二分法(排序的方法) 希望能幫到你?。⊥麀~點(diǎn)贊

JAVA歸并排序有兩行代碼看不懂，麻煩幫忙解釋下

因?yàn)閙erge方法是對(duì)數(shù)組a從索引lower到upper之間的元素排序，不是對(duì)整個(gè)數(shù)組排序，也就是說(shuō)lower的值不一定是0，你可以debug看一看。如果a[lower++] = temp[x];寫(xiě)成a[x] = temp[x]的話就會(huì)有問(wèn)題，因?yàn)閤是從0開(kāi)始的，那么每次排序結(jié)束后temp的元素寫(xiě)回?cái)?shù)組a時(shí)都會(huì)從頭開(kāi)始寫(xiě)，最終不僅排序結(jié)果錯(cuò)誤，而且會(huì)導(dǎo)致原有的元素都會(huì)丟失。

Java 合并排序 求程序

百度文庫(kù)找了一個(gè)

四、合并排序 1、基本思想

合并排序的基本操作是：首先將待排序序列劃分為兩個(gè)長(zhǎng)度相等的子序列；然后分別對(duì)兩個(gè)子序列進(jìn)行歸并排序，得到兩個(gè)有序的子序列；最后將兩個(gè)有序的子序列合并成一個(gè)有序數(shù)列。

MergeSort(A[2*n]) {

divide A[2*n] into A[1,……,n],A[n-1,……,2*n];//劃分 MergeSort(A[1,……,n]);//歸并排序前半個(gè)子序列

MergeSort(A[[n-1,……,2*n]);//歸并排序后半個(gè)子序列 Merge;//合并 }

2、算法復(fù)雜度分析

合并步的時(shí)間復(fù)雜度為O(n)。合并排序算法的時(shí)間復(fù)雜度為O(nlog2n)。

3、編程實(shí)現(xiàn)

public int[] MergeSort(int[] A, int[] tempA, int s, int t){

//如果序列中有一個(gè)以上的元素，即st則進(jìn)行排序

if(s t){

int center = (s + t) / 2;

MergeSort(A, tempA, s, center)

;//歸并排序前半個(gè)子序列

MergeSort(A, tempA, center + 1, t);

//歸并排序后半個(gè)子序列

Merge(A,tempA, s, center, t);

//合并

}

return tempA;

}

public int[] Merge(int[] A, int[] tempA, int s, int m, int t){ int n = t- s + 1;

//n為數(shù)據(jù)總個(gè)數(shù)

int i=s;j=m+1;k=s

while(i = m j = t){

//取A[i]和A[j]中較小者放入tempA[k]

if(A[i]=A[j]){

tempA[k++] = A[i++]; }

else{

tempA[k++] = A[j++]; } }

if(i=m) while(i=m)

tempA[k++]=A[i++];//處理前一個(gè)子序列

else while(j=t)

tempA[k++]=A[j++];//處理后一個(gè)子序列

return tempA;

}

歸并排序的示例代碼

歸并排序原理

歸并排序具體工作原理如下（假設(shè)序列共有n個(gè)元素）：

將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge)，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素

將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素

重復(fù)步驟2，直到所有元素排序完畢

示例代碼

Go語(yǔ)言 func?mergeSort(r?[]int)?[]int?{????length?:=?len(r)???????if?length?=?1?{????????return?r?????}???????num?:=?length?/?2????left?:=?mergeSort(r[:num])???????right?:=?mergeSort(r[num:])???????return?merge(left,?right)}func?merge(left,?right?[]int)?(result?[]int)?{???????l,?r?:=?0,?0???????for?l??len(left)??r??len(right)?{????????if?left[l]??right[r]?{?????????????????????result?=?append(result,?left[l])?????????????????????l++??????????????}?else?{?????????????????????result?=?append(result,?right[r])?????????????????????r++??????????????}???????}???????result?=?append(result,?left[l:]...)???????result?=?append(result,?right[r:]...)???????return}Java語(yǔ)言 package　algorithm;public　class　MergeSort　{????//　private　static　long　sum　=　0;????/**????　*　pre????　*　二路歸并????　*　原理：將兩個(gè)有序表合并和一個(gè)有序表????　*　/pre????　*　????　*　@param　a????　*　@param　s????　*　第一個(gè)有序表的起始下標(biāo)????　*　@param　m????　*　第二個(gè)有序表的起始下標(biāo)????　*　@param　t????　*　第二個(gè)有序表的結(jié)束小標(biāo)????　*　????　*/????private　static　void　merge(int[]　a,　int　s,　int　m,　int　t)　{????????int[]　tmp　=　new　int[t　-　s　+　1];????????int　i　=　s,　j　=　m,　k　=　0;????????while　(i　　m　　j　=　t)　{????????????if　(a[i]　=　a[j])　{????????????????tmp[k]　=　a[i];????????????????k++;????????????????i++;????????????}　else　{????????????????tmp[k]　=　a[j];????????????????j++;????????????????k++;????????????}????????}????????while　(i　　m)　{????????????tmp[k]　=　a[i];????????????i++;????????????k++;????????}????????while　(j　=　t)　{????????????tmp[k]　=　a[j];????????????j++;????????????k++;????????}????????System.arraycopy(tmp,　0,　a,　s,　tmp.length);????}????/**????　*　????　*　@param　a????　*　@param　s????　*　@param　len????　*　每次歸并的有序集合的長(zhǎng)度????　*/????public　static　void　mergeSort(int[]　a,　int　s,　int　len)　{????????int　size　=　a.length;????????int　mid　=　size　/　(len　　1);????????int　c　=　size　　((len　　1)　-　1);????????//　-------歸并到只剩一個(gè)有序集合的時(shí)候結(jié)束算法-------//????????if　(mid　==　0)????????????return;????????//　------進(jìn)行一趟歸并排序-------//????????for　(int　i　=　0;　i　　mid;　++i)　{????????????s　=　i　*　2　*　len;????????????merge(a,　s,　s　+　len,　(len　　1)　+　s　-　1);????????}????????//　-------將剩下的數(shù)和倒數(shù)一個(gè)有序集合歸并-------//????????if　(c　!=　0)????????????merge(a,　size　-　c　-　2　*　len,　size　-　c,　size　-　1);????????//　-------遞歸執(zhí)行下一趟歸并排序------//????????mergeSort(a,　0,　2　*　len);????}????public　static　void　main(String[]　args)　{????????int[]　a　=　new　int[]　{　4,　3,　6,　1,　2,　5　};????????mergeSort(a,　0,　1);????????for　(int　i　=　0;　i　　a.length;　++i)　{????????????System.out.print(a[i]　+);????????}????}}Python語(yǔ)言 def?MergeSort(lists):????if?len(lists)?=?1:????????return?lists????num?=?int(?len(lists)/2?)????left?=?MergeSort(lists[:num])????right?=?MergeSort(lists[num:])????return?Merge(left,?right)def?Merge(left,right):????r,?l=0,?0????result=[]????while?llen(left)?and?rlen(right):????????if?left[l]??right[r]:????????????result.append(left[l])????????????l?+=?1????????else:????????????result.append(right[r])????????????r?+=?1????result?+=?right[r:]????result+=?left[l:]????return?resultprint?MergeSort([1,?2,?3,?4,?5,?6,?7,?90,?21,?23,?45])C語(yǔ)言 #include?stdlib.h#include?stdio.hvoid?Merge(int?sourceArr[],int?tempArr[],?int?startIndex,?int?midIndex,?int?endIndex){????int?i?=?startIndex,?j=midIndex+1,?k?=?startIndex;????while(i!=midIndex+1??j!=endIndex+1)????{????????if(sourceArr[i]?=?sourceArr[j])????????????tempArr[k++]?=?sourceArr[j++];????????else????????????tempArr[k++]?=?sourceArr[i++];????}????while(i?!=?midIndex+1)????????tempArr[k++]?=?sourceArr[i++];????while(j?!=?endIndex+1)????????tempArr[k++]?=?sourceArr[j++];????for(i=startIndex;?i=endIndex;?i++)????????sourceArr[i]?=?tempArr[i];}//內(nèi)部使用遞歸void?MergeSort(int?sourceArr[],?int?tempArr[],?int?startIndex,?int?endIndex){????int?midIndex;????if(startIndex??endIndex)????{????????midIndex?=?(startIndex?+?endIndex)?/?2;????????MergeSort(sourceArr,?tempArr,?startIndex,?midIndex);????????MergeSort(sourceArr,?tempArr,?midIndex+1,?endIndex);????????Merge(sourceArr,?tempArr,?startIndex,?midIndex,?endIndex);????}}int?main(int?argc,?char?*?argv[]){????int?a[8]?=?{50,?10,?20,?30,?70,?40,?80,?60};????int?i,?b[8];????MergeSort(a,?b,?0,?7);????for(i=0;?i8;?i++)????????printf(%d?,?a[i]);????printf(\n);????return?0;}PHP語(yǔ)言 //merge函數(shù)將指定的兩個(gè)有序數(shù)組(arr1arr2,)合并并且排序//我們可以找到第三個(gè)數(shù)組,然后依次從兩個(gè)數(shù)組的開(kāi)始取數(shù)據(jù)哪個(gè)數(shù)據(jù)小就先取哪個(gè)的,然后刪除掉剛剛?cè)∵^(guò)///的數(shù)據(jù)functional_merge($arrA,$arrB){????$arrC?=?array();????while(count($arrA)??count($arrB)){????????//這里不斷的判斷哪個(gè)值小,就將小的值給到arrC,但是到最后肯定要剩下幾個(gè)值,????????//不是剩下arrA里面的就是剩下arrB里面的而且這幾個(gè)有序的值,肯定比arrC里面所有的值都大所以使用????????$arrC[]?=?$arrA['0']??$arrB['0']???array_shift($arrA)?:?array_shift($arrB);????}????returnarray_merge($arrC,?$arrA,?$arrB);}//歸并排序主程序functional_merge_sort($arr){????$len=count($arr);????if($len?=?1)????????return?$arr;//遞歸結(jié)束條件,到達(dá)這步的時(shí)候,數(shù)組就只剩下一個(gè)元素了,也就是分離了數(shù)組????$mid?=?intval($len/2);//取數(shù)組中間????$left_arr?=?array_slice($arr,?0,?$mid);//拆分?jǐn)?shù)組0-mid這部分給左邊left_arr????$right_arr?=?array_slice($arr,?$mid);//拆分?jǐn)?shù)組mid-末尾這部分給右邊right_arr????$left_arr?=?al_merge_sort($left_arr);//左邊拆分完后開(kāi)始遞歸合并往上走????$right_arr?=?al_merge_sort($right_arr);//右邊拆分完畢開(kāi)始遞歸往上走????$arr=al_merge($left_arr,?$right_arr);//合并兩個(gè)數(shù)組,繼續(xù)遞歸????return?$arr;}$arr?=?array(12,?5,?4,?7,?8,?3,?4,?2,?6,?4,?9);print_r(al_merge_sort($arr));Pascal語(yǔ)言 program　mergesort_1;const　maxn=7;type　arr=array[1..maxn]　of　integer;var　a,b,c:arr;i:integer;procedure　merge(r:arr;l,m,n:integer;varr2:arr);var　i,j,k,p:integer;begin　i:=l;　j:=m+1;　k:=l-1;　while　(i=m)　and　(j=n)　do　begin　k:=k+1;　if　r[i]=r[j]　then　begin　r2[k]:=r[i];　i:=i+1　end　else　begin　r2[k]:=r[j];　j:=j+1;　end　end;　if　i=m　then　for　p:=i　to　m　do　begin　k:=k+1;　r2[k]:=r[p];　end;　if　j=n　then　for　p:=j　to　n　do　begin　k:=k+1;　r2[k]:=r[p];　end;end;procedure　mergesort(var　r,r1:arr;s,t:integer);var　k:integer;c:arr;begin　if　s=t　then　r1[s]:=r[s]　else　begin　k:=(s+t)div2;　mergesort(r,c,s,k);　mergesort(r,c,k+1,t);　merge(c,s,k,t,r1)　end;end;begin　write('Enterdata:');　for　i:=1　to　maxn　do　read(a[i]);　mergesort(a,b,1,maxn);　for　i:=1　to　maxn　do　write(b[i]:9);　writeln;end.//============================================program　mergesort_2;const　max=100000;var　a,r:array[1..max]　of　long　int;n,i:long　int;procedure　msort(s,t:longint);var　m,i,j,k:long　int;begin　if　s=t　then　exit;　m:=(s+t)div2;　msort(s,m);　msort(m+1,t);　i:=s;　j:=m+1;　k:=s;　while　(i=m)　and　(j=t)　do　begin　if　a[i]a[j]　then　begin　r[k]:=a[i];　inc(i);　inc(k);　end　else　begin　r[k]:=a[j];　inc(j);　inc(k);　end;　end;　while　i=m　do　begin　r[k]:=a[i];　inc(i);　inc(k);　end;　while　j=t　do　begin　r[k]:=a[j];　inc(j);　inc(k);　end;　for　i:=s　to　t　do　a[i]:=r[i];end;begin　readln(n);　for　i:=1　to　n　do　read(a[i]);　msort(1,n);　for　i:=1　to　n　do　writeln(a[i]);end.Basic語(yǔ)言 Sub?MergeSort(Array()?As?Integer,?First?As?Integer,?Last?As?Integer)Dim?mid?As?Integer?=?0If?firstlast?Then?mid?=?(first+last)\?2MergeSort(Array,?first,?mid);MergeSort(Array,?mid+1,?last);Merge(Array,?first,?mid,?last);End?IfEnd?Sub/*以下示例代碼實(shí)現(xiàn)了歸并操作。array[]是元素序列，其中從索引p開(kāi)始到q位置，按照升序排列，同時(shí)，從(q+1)到r也已經(jīng)按照升序排列，merge()函數(shù)將把這兩個(gè)已經(jīng)排序好的子序列合并成一個(gè)排序序列。結(jié)果放到array中。*//***?0?=?p?=?q??r,?subarray?array[p..q]?and?array[q+1..r]?are?already?sorted.*?the?merge()?function?merges?the?two?sub-arrays?into?one?sorted?array.*/void?Merge(int?array[],?int?p,?int?q,?int?r){????int?i,k;????int?begin1,end1,begin2,end2;????int*?temp?=?(int*)malloc((r-p+1)*sizeof(int));????begin1?=?p;????end1???=?q;????begin2?=?q+1;????end2???=?r;????k?=?0;????while((begin1?=?end1)(?begin2?=?end2))????{????????if(array[begin1]?=?array[begin2]){?????????????temp[k]?=?array[begin1];????????????begin1++;????????}????????else????????{????????????temp[k]?=?array[begin2];????????????begin2++;????????}????????k++;????}????while(begin1=end1?||?begin2=end2)????{????????if(begin1=end1)????????{????????????temp[k++]?=?array[begin1++];????????}????????if(begin2=end2)????????{????????????temp[k++]?=?array[begin2++];????????}????????}????????for?(i?=?0;?i??=(r?-?p);?i++)????????????array[p+i]?=?temp[i];????free(temp);}JavaScript語(yǔ)言

使用遞歸的代碼如下。優(yōu)點(diǎn)是描述算法過(guò)程思路清晰，缺點(diǎn)是使用遞歸，mergeSort()函數(shù)頻繁地自我調(diào)用。長(zhǎng)度為n的數(shù)組最終會(huì)調(diào)用mergeSort()函數(shù) 2n-1次，這意味著一個(gè)長(zhǎng)度超過(guò)1500的數(shù)組會(huì)在Firefox上發(fā)生棧溢出錯(cuò)誤。可以考慮使用迭代來(lái)實(shí)現(xiàn)同樣的功能。 function　merge(left,?right){????var　result=[];????while(left.length0??right.length0){????????if(left[0]right[0]){????????/*shift()方法用于把數(shù)組的第一個(gè)元素從其中刪除，并返回第一個(gè)元素的值。*/????????????result.push(left.shift());????????}else{????????????result.push(right.shift());????????}????}????return　result.concat(left).concat(right);}function　mergeSort(items){????if(items.length?==?1){????????return　items;}var　middle?=?Math.floor(items.length/2),????left?=?items.slice(0,?middle),????right?=?items.slice(middle);????return　merge(mergeSort(left),?mergeSort(right));}非遞歸算法（C++） #includeiostream#includectime#includecstring#includecstdlibusing?namespace?std;/**將a開(kāi)頭的長(zhǎng)為length的數(shù)組和b開(kāi)頭長(zhǎng)為right的數(shù)組合并n為數(shù)組長(zhǎng)度，用于最后一組*/void　Merge(int*　data,int　a,int　b,int　length,int　n){　int　right;　if(b+length-1?=?n-1)　right?=?n-b;　else　right?=?length;　int*　temp?=?new　int[length+right];　int　i=0,?j=0;　while(i=length-1??j=right-1){????　if(data[a+i]?=?data[b+j]){????　????temp[i+j]?=?data[a+i];i++;??????}????　else{????????temp[i+j]?=?data[b+j];????????j++;??????}　}　if(j?==?right){//a中還有元素，且全都比b中的大,a[i]還未使用　??memcpy(temp?+?i?+?j,?data?+?a?+?i,?(length?-?i)?*?sizeof(int));　}??else?if(i?==?length){??????memcpy(temp?+?i?+?j,?data?+?b?+?j,?(right?-?j)*sizeof(int));??}　memcpy(data+a,?temp,?(right?+?length)?*?sizeof(int));　delete?[]?temp;}void　MergeSort(int*　data,?int　n){　int　step?=?1;　while(step??n){????　for(int　i=0;?i=n-step-1;?i+=2*step)????　????Merge(data,?i,?i+step,?step,?n);????//將i和i+step這兩個(gè)有序序列進(jìn)行合并????//序列長(zhǎng)度為step????//當(dāng)i以后的長(zhǎng)度小于或者等于step時(shí)，退出????　step*=2;//在按某一步長(zhǎng)歸并序列之后，步長(zhǎng)加倍　}}int　main(){　int　n;　cinn;　int*　data?=?new　int[n];　if(!data)　exit(1);　int　k?=?n;　while(k--){　????cindata[n-k-1];　}　clock_t　s?=?clock();　MergeSort(data,?n);　clock_t　e?=?clock();　k=n;　while(k--){　????coutdata[n-k-1]'?';　}　coutendl;　coutthe?algorithm?usede-smiliseconds.endl;　delete　data;　return　0;}二路歸并

ConstFI='in.txt';FO='out.txt';MaxN=10000;TypeTIndex=Longint;TDat=Array[0..MaxN]OfTIndex;VarN:TIndex;Dat:TDat;Tmp:TDat;ProcedureMerge(L,Mid,R:TIndex);VarP1,P2:TIndex;E1,E2:TIndex;P:TIndex;I:TIndex;BeginP1:=L;P2:=Mid+1;P:=L;RepeatIf(Dat[P1]=Dat[P2])ThenBeginTmp[P]:=Dat[P1];Inc(P1);Inc(P);EndElseBeginTmp[P]:=Dat[P2];Inc(P2);Inc(P);End;Until(P1=Mid+1)Or(P2=R+1);If(P1=Mid+1)ThenBeginE1:=P2;E2:=R;EndElseBeginE1:=P1;E2:=Mid;End;ForI:=E1ToE2DoBeginTmp[P]:=Dat[I];Inc(P);End;End;ProcedureSort(L,R:TIndex);VarMid:TIndex=0;BeginMid:=(L+R)Shr1;If(LMid)ThenSort(L,Mid);If(Mid+1R)ThenSort(Mid+1,R);Merge(L,Mid,R);ForMid:=LToRDoDat[Mid]:=Tmp[Mid];End;ProcedureInit;VarI:TIndex;BeginFillChar(Dat,SizeOf(Dat),0);Readln(N);ForI:=1ToNDoRead(Dat[I]);End;ProcedureMain;BeginSort(1,N);End;ProcedureFinal;VarI:TIndex;BeginForI:=1ToNDoWrite(Dat[I],'');Writeln;End;BeginAssign(Input,FI);Assign(Output,FO);Reset(Input);Rewrite(Output);Init;Main;Final;Close(Input);Close(Output);End.

Delphi歸并排序完整源代碼例子： //合并子函數(shù)procedureTForm1.MergePass(vardatas:arrayofInteger;left,mid,right:Integer);vartmpArr:arrayofInteger;arrLen:Integer;i,k:Integer;begin1,begin2,end1,end2:Integer;beginarrLen:=right-left+1;SetLength(tmpArr,arrLen);begin1:=left;end1:=mid;begin2:=mid+1;end2:=right;k:=0;while((begin1=end1)and(begin2=end2))dobeginif(datas[begin1]datas[begin2])thenbegintmpArr[k]:=datas[begin1];Inc(begin1);endelsebegintmpArr[k]:=datas[begin2];Inc(begin2);end;inc(k);end;while(begin1=end1)dobegintmpArr[k]:=datas[begin1];Inc(begin1);Inc(k);end;while(begin2=end2)dobegintmpArr[k]:=datas[begin2];Inc(begin2);Inc(k);end;fori:=0to(right-left)dobegindatas[left+i]:=tmpArr[i];end;end;//排序主函數(shù)，left是數(shù)組左下標(biāo)，0開(kāi)始。right是數(shù)組右下標(biāo)。procedureTForm1.MergeSort(vardatas:arrayofInteger;left,right:Integer);varmid:Integer;i:Integer;beginmid:=0;if(leftright)thenbeginmid:=(right+left)div2;showLog('中間索引：'+inttostr(mid));MergeSort(datas,left,mid);MergeSort(datas,mid+1,right);MergePass(datas,left,mid,right);showLog('---'+getArrayString(datas));//顯示數(shù)組中間狀態(tài)end;end;//調(diào)用方法：procedureTForm1.btn1Click(Sender:TObject);varinArr:array[0..9]ofInteger;beginCopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);showLog('輸入數(shù)據(jù)：'+getArrayString(inArr));MergeSort(inArr,0,High(inArr));showLog('輸出數(shù)據(jù)：'+getArrayString(inArr));end;