Merge-sort-example.gif
public class MergeSort {
public static void mergeSort(int[] arr) {
mSort(arr, 0, arr.length - 1);
}
/**
* 遞歸分治
*
* @param arr 待排數(shù)組
* @param left 左指針
* @param right 右指針
*/
public static void mSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mSort(arr, left, mid); //遞歸排序左邊
mSort(arr, mid + 1, right); //遞歸排序右邊
merge(arr, left, mid, right); //合并
}
/**
* 合并兩個(gè)有序數(shù)組
*
* @param arr 待合并數(shù)組
* @param left 左指針
* @param mid 中間指針
* @param right 右指針
*/
public static void merge(int[] arr, int left, int mid, int right) {
//[left, mid] [mid+1, right]
int[] tempArray = new int[right - left + 1]; //中間數(shù)組
int leftIndexFromLeft = left; //左邊序列左指針
int leftIndexFromRight = mid + 1; //右邊序列左指針
int tempArrIndex = 0;
//左序列左指針在左序列范圍之內(nèi)各淀，右序列左指針在右序列范圍之內(nèi)
while (leftIndexFromLeft <= mid && leftIndexFromRight <= right) {
//比較左序列左指針對(duì)應(yīng)數(shù)字和右序列左指針對(duì)應(yīng)數(shù)字玉罐，選擇較小的數(shù)字移動(dòng)到臨時(shí)數(shù)組內(nèi)
// if (arr[leftIndexFromLeft] <= arr[leftIndexFromRight]) {
// tempArray[tempArrIndex++] = arr[leftIndexFromLeft++];
// } else {
// tempArray[tempArrIndex++] = arr[leftIndexFromRight++];
// }
tempArray[tempArrIndex++] = arr[leftIndexFromLeft] <= arr[leftIndexFromRight] ?
arr[leftIndexFromLeft++] : arr[leftIndexFromRight++];
}
while (leftIndexFromLeft <= mid) {
//合并左序列左指針右側(cè)剩余的數(shù)字到臨時(shí)數(shù)組
tempArray[tempArrIndex++] = arr[leftIndexFromLeft++];
}
while (leftIndexFromRight <= right) {
//合并右序列右指針右側(cè)剩余的數(shù)字到臨時(shí)數(shù)組
tempArray[tempArrIndex++] = arr[leftIndexFromRight++];
}
for (int p = 0; p < tempArray.length; p++) {
arr[left + p] = tempArray[p]; //復(fù)制臨時(shí)數(shù)組內(nèi)的元素到原數(shù)組內(nèi)
}
}
}
