java實現(xiàn)歸并排序問題

public void mySort(int low,int high){

頭屯河ssl適用于網站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)建站的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

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

}

}

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

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ù)復制進c中。這里面關鍵的一點就是使用了3個臨時變量，用于標志每個數(shù)組對應的位置，這樣子可以極大簡化我們的代碼設計。下面是對應的圖示過程：

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

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

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

第三部：調用上面的合并方法合并起來即可

代碼非常簡單，直接貼上

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

}

}

}

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

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

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

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

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

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

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

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

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

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

2. 算法步驟

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

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

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

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

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

3. 動圖演示

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

var len = arr. length ;

if ( len

當前標題：java遞歸歸并排序代碼 java歸并排序簡單代碼
標題路徑：http://jinyejixie.com/article40/dodhdho.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供品牌網站制作、網站改版、做網站、電子商務、App開發(fā)、移動網站建設

廣告

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