java中遞歸歸並排序算法程序代碼

 　　遞歸歸並排序： 核心思想就是將兩個已經各自排好順序的數組合並成一個。這樣我們遞歸的將一個大的數組，不斷分成2段，直到每個數組只有一個元素。同時也不斷合並已經排好順序的數組，直到全都合並完成

　　java實現遞歸歸並排序代碼：

 代碼如下   import java.util.*;
 
public class MergeSortTest{
 
 
 
 public static void main(String[] args){
 int arr[]  = new int[]{10,9,12,4,11,7,8,3};
 Sort(arr);
 System.out.println(Arrays.toString(arr));  //將整型數組轉換為String，打印出來 
 
 }
 
 
 
 
 
 public static void Sort(int  arr[]){
 int tmpArray[] = new int[arr.length]; //創建一個臨時的數組來存放臨時排序的數組 
 mergeSort(arr,tmpArray, 0 ,arr.length-1); //開始對數組歸並排序 
 
 
 }
 //用遞歸的方法，對數組進行歸並排序    
 private static void mergeSort(int arr[],int tmpArray[],int first ,int last){
 if(first<last){ //   確定數組不是空的 
 int mid =(first+last)/2;   //將數組分成兩段  
 //下面是用遞歸的方法，不斷分割數組。即1分2，2分4，以此類推。直到每個數組都只剩下2個元素。
 mergeSort(arr,tmpArray,first,mid);
 mergeSort(arr,tmpArray,mid+1,last);
 // 下面是利用臨時數組tmpArray[] 對分割後的數組排序和歸並
 merge(arr,tmpArray,first,mid,last);
 System.out.println(Arrays.toString(arr)); 
 }
 }
 
 private static  void merge(int a[],int tmpArray[],int first,int mid,int last){
 int beginHalf1 = first; //   第一段數組的起始元素下標 
 int endHalf1 = mid; //   第一段數組的末尾元素下表 
 int beginHalf2 = mid+1; //   第二段數組的起始元素下標 
 int endHalf2 = last; //   第二段數組的末尾元素下標 
 int index = beginHalf1;  //   臨時數組的索引 
 int num = last - first+1; //   將臨時數組tmpArray中已經排好順序的元素拷貝到數組arr[]需要的次數， (其中沒有排好順序的元素自然就不用復制過去，所以arr那些沒有排序的元素還是原樣。
 
 while((beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2)){ // 確認分割後的兩段數組是否都取到了最後一個元素
 if(a[beginHalf1] <= a[beginHalf2]){ //   分別到兩段數組中抽取兩個元素的值進行比較 
 //哪那個元素值小，就復制到臨時數組tmpArray對應的位置中，然後index++，同時將那段數組再去下一個元素
 
 tmpArray[index++] = a[beginHalf1++];
 }
 else{
 tmpArray[index++] = a[beginHalf2++];
 
 }
 
 }
 //經過上面的while循環，必定有段數組的元素都取光了,即肯定還有一段數組是沒有取光的，不但沒取光，而且剩下的元素還已經排完序了。所以下面兩個while只有一個會執行，就是將剩下的那段數組的已經排好順序的元素都拷貝到臨時數組tmpArray[]中對應的位置。 
 
 while(beginHalf1 <= endHalf1){
 tmpArray[index++] = a[beginHalf1++];
 }
 while(beginHalf2 <= endHalf2){
 tmpArray[index++] = a[beginHalf2++];
 }
 //   將臨時數組tmpArray[]中的已經排好順序的元素全都拷貝到原來的數組arr[]中
 for(int i = 0 ; i < num ;i++,endHalf2--){
 a[endHalf2] = tmpArray[endHalf2];
 }
 
 
 }
 
}
輸出結果如下：
[9, 10, 12, 4, 11, 7, 8, 3]
[9, 10, 4, 12, 11, 7, 8, 3]
[4, 9, 10, 12, 11, 7, 8, 3]
[4, 9, 10, 12, 7, 11, 8, 3]
[4, 9, 10, 12, 7, 11, 3, 8]
[4, 9, 10, 12, 3, 7, 8, 11]
[3, 4, 7, 8, 9, 10, 11, 12]
[3, 4, 7, 8, 9, 10, 11, 12]