遞歸歸並排序： 核心思想就是將兩個已經各自排好順序的數組合並成一個。這樣我們遞歸的將一個大的數組，不斷分成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]
