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

創(chuàng)新互聯(lián)主要從事成都做網(wǎng)站、網(wǎng)站設計、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務龍山,10多年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:13518219792

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

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

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

在《數(shù)據(jù)結(jié)構與算法 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) 的時間復雜度。代價是需要額外的內(nèi)存空間。

2. 算法步驟

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

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

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

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

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

3. 動圖演示

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

var len = arr. length ;

if ( len

java 編寫一個程序,輸入3個整數(shù),然后程序?qū)@三個整數(shù)按照從大到小進行排列

可以實現(xiàn)比較器Comparator來定制排序方案，同時使用Colletions.sort的方式進行排序，代碼如下：

public void sortDesc(ListLong s){

Collections.sort(s, new ComparatorLong() {

public int compare(Long o1, Long o2) {

Long result = o2 - o1;

return result.intValue();

}

});

s.forEach(item-{

System.out.print(item +" ");

});

}

同時常用的比較排序算法主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等。

java的冒泡排序?qū)崿F(xiàn)如下：

public?static?void?bubbleSort(int?[]arr)?{????????for(int?i?=0;iarr.length-1;i++)?{????????????for(int?j=0;jarr.length-i-1;j++)?{//-1為了防止溢出????????????????if(arr[j]arr[j+1])?{????????????????????int?temp?=?arr[j];?????????????????????????????????????????arr[j]=arr[j+1];?????????????????????????????????????????arr[j+1]=temp;????????????}????????????}????????????}????}

還有非比較排序，時間復雜度可以達到O(n)，主要有：計數(shù)排序，基數(shù)排序，桶排序等。

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