以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(gap>0){ 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);//輸出當前進行插入排序的數組。 console.log(arr);//輸出此輪排序後的數組。 } 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。依次對這些間隔的數組插入排序。
間隔為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.快速排序。把一個數組以數組中的某個值為標記。比這個值小的放到數組的左邊，比這個值得大的放到數組的右邊。然後再遞歸 對左邊和右邊的數組進行同樣的操作。直到排序完成。通常以數組的第一個值為標記。
代碼:
function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tag; if(len<2){ return arr; } tag = arr[0]; for(i=1;i<len;i++){ if(arr[i]<=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]); } } return quickSort(leftArr).concat(tag,quickSort(rightArr)); }
3.歸並排序。把一系列排好序的子序列合並成一個大的完整有序序列。從最小的單位開始合並。然後再逐步合並合並好的有序數組。最終實現歸並排序。
合並兩個有序數組的方法：
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(gap<maxgap){ 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];
❷ 使用java歸並排序
你打開JDK的src.zip看一下Arrays類的原碼，Arrays類的sort方法用的就是歸並。
所以俺從來不費這個腦筋，吼吼~~
❸ 求java實現二路歸並的程序
packagealgorithm;
publicclassMergeSort{
//privatestaticlongsum=0;
/**
*<pre>
*二路歸並
*原理：將兩個有序表合並和一個有序表
*</pre>
*
*@parama
*@params
*第一個有序表的起始下標
*@paramm
*第二個有序表的起始下標
*@paramt
*第二個有序表的結束小標
*
*/
privatestaticvoidmerge(int[]a,ints,intm,intt){
int[]tmp=newint[t-s+1];
inti=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.array(tmp,0,a,s,tmp.length);
}
/**
*
*@parama
*@params
*@paramlen
*每次歸並的有序集合的長度
*/
publicstaticvoidmergeSort(int[]a,ints,intlen){
intsize=a.length;
intmid=size/(len<<1);
intc=size&((len<<1)-1);
//-------歸並到只剩一個有序集合的時候結束演算法-------//
if(mid==0)
return;
//------進行一趟歸並排序-------//
for(inti=0;i<mid;++i){
s=i*2*len;
merge(a,s,s+len,(len<<1)+s-1);
}
//-------將剩下的數和倒數一個有序集合歸並-------//
if(c!=0)
merge(a,size-c-2*len,size-c,size-1);
//-------遞歸執行下一趟歸並排序------//
mergeSort(a,0,2*len);
}
publicstaticvoidmain(String[]args){
int[]a=newint[]{4,3,6,1,2,5};
mergeSort(a,0,1);
for(inti=0;i<a.length;++i){
System.out.print(a[i]+"");
}
}
}
❹ java歸並排序演算法 在哪個包里
分而治之(divide - conquer);每個遞歸過程涉及三個步驟
第一, 分解: 把待排序的 n 個元素的序列分解成兩個子序列, 每個子序列包括 n/2 個元素.
第二, 治理: 對每個子序列分別調用歸並排序MergeSort, 進行遞歸操作
第三, 合並: 合並兩個排好序的子序列,生成排序結果.
public static void mergeSort(int[] a, int[] tmp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, tmp, left, mid);// 左排序
mergeSort(a, tmp, mid + 1, right);// 右排序
merge(a, tmp, left, mid + 1, right);// 左右合並
}
}
public static void merge(int[] a, int[] tmp, int left, int rightPos,
int right) {
int leftEnd = rightPos - 1;
int tmpPos = left;
int num = right - left + 1;
while (left <= leftEnd && rightPos <= right) {
if (a[left] < a[rightPos]) {
tmp[tmpPos++] = a[left++];
} else {
tmp[tmpPos++] = a[rightPos++];
}
}
while (left <= leftEnd) {
tmp[tmpPos++] = a[left++];
}
while (rightPos <= right) {
tmp[tmpPos++] = a[rightPos++];
}
for (int i = 0; i < num; i++, right--) {
a[right] = tmp[right];
}
}
❺ 歸並排序java多次合並是怎麼實現的就是那個merge方法是執行三次拆分後再三次歸並嗎
你好，其實是用了分治的思想，每次都進行拆分，直到可以比較為止，然後逐步合並，擴大排序集合！
❻ java 實現歸並排序，我為什麼錯了！555……代碼如下，沒找到錯誤啊~~~求高手解答！！小女子不勝感激~
你是女生啊！哈哈！給我講講這演算法的原理！我幫你看看代碼！
❼ Java可以實現原地歸並演算法么
歸並演算法么，比如合並兩個有序的數組成為一個新的有序數組
❽ java實現歸並排序問題
public void mySort(int low,int high){
int lo=low;
int hi=high;
if (lo>=hi) {
return;
}else{
boolean flag=false;
while (lo<hi) {
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實現歸並排序問題，請大家幫我看代碼錯在哪裡
在29行是數組越界。
❿ 關於歸並排序的問題（java實現）
在計算機科學中，復歸並排制序（通常拼寫為mergesort）是一種有效的，通用的，基於比較的排序演算法。 大多數實現產生穩定的排序，這意味著實現保留排序輸出中相等元素的輸入順序。 合並排序是一種分而治之的演算法，由John von Neumann於1945年發明。自1948年Goldstine和von Neumann的報告中出現了自下而上合並的詳細描述和分析。下面小編將詳細介紹該演算法的原理及實現過程。
1/6 分步閱讀
歸並演算法的具體步驟，歸並排序函數如下：
MergeSort(arr[], l, r)
1、找到一個數組中中間的點將數組分成兩個部分
middle m = (l+r)/2
2、遞歸調用MergeSort函數取第一部分
Call mergeSort(arr, l, m)
3、遞歸調用MergeSort函數取第二部分
Call mergeSort(arr, m+1, r)
4、使用merge函數融合排序步驟2和步驟3中的子數組
Call merge(arr, l, m, r)。