排序算法之2路歸并排序（遞歸和非遞歸）

歸并排序，從字面意思上了解，即合并的時候排序。

歸并排序是分治法的一種，首先将待排數列分成1個一個元素，然後依次按大小合并。

排序過程

分

初始關鍵值  [49]  [38]  [65]  [97]  [76]  [13]  [27] 

合                         

第一趟歸并：(38,49)   (65,97)    (13,76)     27

第三趟歸并：(38,49,65,97)         (13,27,76)

第四趟合并：[13,27,38,49,65,76,97]

代碼：

package merge;

import java.util.Arrays;

public class MergeSort {

public static void main(String[] args) {

int x[]={4,-5,0,3,-1,12,9,-7,8,-4,11};  

int []a = new int[]{33,9,34,12,6,10,8,9,32,1};

int[] b = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11 };

MergeSort sort = new MergeSort();

sort.NMergeSort(x);

System.out.println(Arrays.toString(x));

sort.mergeSort(a, 0, a.length - 1);

System.out.println(Arrays.toString(a));

System.out.println();

sort.mergeSort(b,0,a.length - 1);

System.out.println(Arrays.toString(b));

}

public void merge(int []a,int low,int middle,int high){//合并

int length = a.length;//将low到Middle ，Middle到high的元素按順序合并

int []b = new int[length];//輔助數組

int k = 0;

int j = middle+1,i = low;

while(i <= middle && j <=high){

if(a[i]<a[j]) b[k++] = a[i++];//比較較小者填入數組

else b[k++] = a[j++];

}

while(i <= middle) b[k++] = a[i++];//若有元素沒有填入完

while(j <= high) b[k++] = a[j++];

for(k = 0,i = low;i <= high;i++,k++){

a[i] = b[k];//将數組重新複制到a數組中

}

}

public void NMergeSort(int []a){

int size=1;//分治元素數量初始為1，按2的幂次遞增

int length = a.length;

int low = 0;

int middle;

int high;

while(size < length){

//分治

low = 0;

while(low + size <= length-1){

middle = low + size - 1;//合并左邊高位下标

high = middle + size;//帶合并右邊數組高位下标

if(high > length - 1){//如果右邊數組中的數值不夠size

high = length - 1;

}

merge(a,low,middle,high);//按size合并

low = high+1;//遞增周遊整個數組

}

size*=2;

}

}

public void mergeSort(int a[],int low,int high){

int middle;

if(low == high) return ;

else{

middle = (low+high)/2;

mergeSort(a, low, middle);//先分治

mergeSort(a,middle+1,high);

merge(a,low,middle,high);//再合并

}

}

}