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ù)排序等。以下是歸并排序算法：

創(chuàng)新互聯(lián)建站是一家集網(wǎng)站建設(shè),宜秀企業(yè)網(wǎng)站建設(shè),宜秀品牌網(wǎng)站建設(shè),網(wǎng)站定制,宜秀網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷(xiāo),網(wǎng)絡(luò)優(yōu)化,宜秀網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專(zhuān)業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

歸并排序（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實(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)贊

歸并排序-merge遞歸

用到遞歸的思想

分成兩半進(jìn)行排序，把結(jié)果進(jìn)行合并(merge),再分成兩半進(jìn)行排序，一直這樣遞歸下去。

時(shí)間和空間消耗比較大。每一次函數(shù)調(diào)用都需要在內(nèi)存棧中分配空間以保存參數(shù)，返回地址以及臨時(shí)變量，而且往棧里面壓入數(shù)據(jù)和彈出都需要時(shí)間。

要注意basecase，終止條件

平均，最好，最壞 O(N*log2N)

不斷分成兩半（分的次數(shù)就是對(duì)數(shù)log2N， 每次又是N 所以就是N*log2N)。

空間復(fù)雜度

O(N)

穩(wěn)定, Java對(duì)象的排序使用mergesort. 改進(jìn)版叫TimSort.

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];

怎樣使用遞歸實(shí)現(xiàn)歸并排序

第一步：先寫(xiě)一個(gè)合并兩個(gè)排序好數(shù)組的方法，方法名就叫做merge，如下：

[java]?view plain?copy

public?static?void?merge(int[]?a,?int?aSize,?int[]?b,?int?bSize,?int[]?c){

int?tempA?=?0,?tempB?=?0,?tempC?=?0;

while(tempA??aSize??tempB??bSize){

if(a[tempA]??b[tempB]){

c[tempC++]?=?b[tempB++];

}else{

c[tempC++]?=?a[tempA++];

}

}

while(tempA??aSize){

c[tempC++]?=?a[tempA++];

}

while(tempB??bSize){

c[tempC++]?=?b[tempB++];

}

這個(gè)方法非常簡(jiǎn)單，一共有著5個(gè)參數(shù)（也可以簡(jiǎn)化為3個(gè)參數(shù)）,其中a，b數(shù)組是待合并數(shù)組，aSize，bSize是數(shù)組長(zhǎng)度（這兩個(gè)參數(shù)可以去掉）,c為目標(biāo)數(shù)組。主要的流程就是不斷的比較a，b數(shù)組的大小，然后將較小數(shù)據(jù)復(fù)制進(jìn)c中。這里面關(guān)鍵的一點(diǎn)就是使用了3個(gè)臨時(shí)變量，用于標(biāo)志每個(gè)數(shù)組對(duì)應(yīng)的位置，這樣子可以極大簡(jiǎn)化我們的代碼設(shè)計(jì)。下面是對(duì)應(yīng)的圖示過(guò)程：

有了這個(gè)方法之后，我們就可以開(kāi)始寫(xiě)歸并排序的主體方法了。寫(xiě)主體方法也很簡(jiǎn)單，思想就是分治算法。

第一步：就是將大數(shù)組分成兩個(gè)小的數(shù)組

第二部：排序這兩個(gè)數(shù)組，使用的是遞歸排序方法，也就是自己調(diào)用自己

第三部：調(diào)用上面的合并方法合并起來(lái)即可

代碼非常簡(jiǎn)單，直接貼上

[java]?view plain?copy

public?class?TowersApp{

public?static?void?main(String[]?args){

int[]?a?=?{1,1,0,1,1,5,3};

mergeSort(a);

for(int?i=0;?ia.length;?i++){

System.out.print(a[i]);

}

}

public?static?void?mergeSort(int[]?source){

//遞歸出口

if(source.length?==?1)?return;

//將大數(shù)組分成兩個(gè)小數(shù)組

int?middle?=?source.length?/?2;

int[]?left?=?new?int[middle];

for(int?i=0;?imiddle;?i++){

left[i]?=?source[i];

}

int[]?right?=?new?int[source.length?-?middle];

for(int?i=middle;?isource.length;?i++){

right[i-middle]?=?source[i];

}

//對(duì)數(shù)據(jù)進(jìn)行排序（這里使用遞歸排序）

mergeSort(left);

mergeSort(right);

//合并排序好的數(shù)據(jù)

merge(left,?left.length,?right,?right.length,?source);

}

public?static?void?merge(int[]?a,?int?aSize,?int[]?b,?int?bSize,?int[]?c){

int?tempA?=?0,?tempB?=?0,?tempC?=?0;

while(tempA??aSize??tempB??bSize){

if(a[tempA]??b[tempB]){

c[tempC++]?=?b[tempB++];

}else{

c[tempC++]?=?a[tempA++];

}

}

while(tempA??aSize){

c[tempC++]?=?a[tempA++];

}

while(tempB??bSize){

c[tempC++]?=?b[tempB++];

}

}

}

總結(jié)：要記住歸并排序算法的核心核心思想：分而治之。

java中歸并排序

1、歸并排序?qū)崿F(xiàn)：

public?static?void?main(String[]?args)?{

int?a[]={1,8,2,6,5,4};

int[]?arr=?sort(a,0,a.length-1);

for(int?rr=0;rr=5;rr++)

System.out.printf("%d\t",?arr[rr]);

System.out.printf("\n");

}

public?static?int[]?sort(int[]?a,int?low,int?high){

int?mid?=?(low+high)/2;

if(lowhigh){

sort(a,low,mid);

sort(a,mid+1,high);

//左右歸并

merge(a,low,mid,high);

}

return?a;

}

public?static?void?merge(int[]?a,?int?low,?int?mid,?int?high)?{

int[]?temp?=?new?int[high-low+1];

int?i=?low;

int?j?=?mid+1;

int?k=0;

//?把較小的數(shù)先移到新數(shù)組中

while(i=mid??j=high){

if(a[i]a[j]){

temp[k++]?=?a[i++];

}else{

temp[k++]?=?a[j++];

}

}

//?把左邊剩余的數(shù)移入數(shù)組?

while(i=mid){

temp[k++]?=?a[i++];

}

//?把右邊邊剩余的數(shù)移入數(shù)組

while(j=high){

temp[k++]?=?a[j++];

}

//?把新數(shù)組中的數(shù)覆蓋nums數(shù)組

for(int?x=0;xtemp.length;x++){

a[x+low]?=?temp[x];

}

}

2、簡(jiǎn)單的數(shù)組排序

public?static?void?main(String[]?args)?{

int?a[]={1,8,2,6,5,4};

Arrays.sort(a);

for(int?rr=0;rr=5;rr++)

System.out.printf("%d\t",?a[rr]);

System.out.printf("\n");

}

網(wǎng)頁(yè)標(biāo)題：歸并排序Java代碼遞歸 歸并排序的代碼
網(wǎng)址分享：http://jinyejixie.com/article22/doscjjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、網(wǎng)站導(dǎo)航、網(wǎng)頁(yè)設(shè)計(jì)公司、微信小程序、網(wǎng)站營(yíng)銷(xiāo)、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)