歸并排序Java代碼遞歸 歸并排序的代碼

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)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是歸并排序算法：

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

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

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

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

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

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

然而，在 JavaScript 中這種方式不太可行，因為這個算法的遞歸深度對它來講太深了。

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

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

2. 算法步驟

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

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

比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

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

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

3. 動圖演示

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

var len = arr. length ;

if ( len

java實現(xià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);

}

}

這里是遞歸加二分法(排序的方法) 希望能幫到你！！望~~點贊

歸并排序-merge遞歸

用到遞歸的思想

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

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

要注意basecase，終止條件

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

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

空間復(fù)雜度

O(N)

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

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

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

1.希爾排序。 希爾排序是在插入排序上面做的升級。是先跟距離較遠的進行比較的一些方法。

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);//輸出當前進行插入排序的數(shù)組。 console.log(arr);//輸出此輪排序后的數(shù)組。 } gap = parseInt(gap/2); } return arr; }

過程輸出：

[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。依次對這些間隔的數(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.快速排序。把一個數(shù)組以數(shù)組中的某個值為標記。比這個值小的放到數(shù)組的左邊，比這個值得大的放到數(shù)組的右邊。然后再遞歸 對左邊和右邊的數(shù)組進行同樣的操作。直到排序完成。通常以數(shù)組的第一個值為標記。

代碼:

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.歸并排序。把一系列排好序的子序列合并成一個大的完整有序序列。從最小的單位開始合并。然后再逐步合并合并好的有序數(shù)組。最終實現(xiàn)歸并排序。

合并兩個有序數(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

看出來從最小的單位入手。

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

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

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

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

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

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

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

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

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

第一步：先寫一個合并兩個排序好數(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++];

}

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

有了這個方法之后，我們就可以開始寫歸并排序的主體方法了。寫主體方法也很簡單，思想就是分治算法。

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

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

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

代碼非常簡單，直接貼上

[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ù)組分成兩個小數(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];

}

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

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、簡單的數(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)頁標題：歸并排序Java代碼遞歸 歸并排序的代碼
網(wǎng)址分享：http://muchs.cn/article22/doscjjc.html

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

廣告

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