歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

*
* @param data
* 數(shù)組對(duì)象
* @param left
* 左數(shù)組的第一個(gè)元素的索引
* @param center
* 左數(shù)組的最后一個(gè)元素的索引，center+1 是右數(shù)組第一個(gè)元素的索引
* @param right
* 右數(shù)組最后一個(gè)元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 臨時(shí)數(shù)組 int[] tmpArr = new int[data.length];
// 右數(shù)組第一個(gè)元素索引
int mid = center + 1;
// third 記錄臨時(shí)數(shù)組的索引
int third = left;
// 緩存左數(shù)組第一個(gè)元素的索引
int tmp = left; while (left <= center && mid <= right) {
// 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組
if (data[left] <= data[mid]) { tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè) while 只會(huì)執(zhí)行其中一個(gè)）
while (mid <= right) { tmpArr[third++] = data[mid++];
public class MergeSortTest {
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; print(data);
mergeSort(data);
System.out.println("排序后的數(shù)組：");
print(data);
}
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) { if (left >= right)
return;
// 找出中間索引
int center = (left + right) / 2;
// 對(duì)左邊數(shù)組進(jìn)行遞歸
sort(data, left, center);
// 對(duì)右邊數(shù)組進(jìn)行遞歸
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
print(data);
}
/**
* 將兩個(gè)數(shù)組進(jìn)行歸并，歸并前面 2 個(gè)數(shù)組已有序，歸并后依然有序
*
* @param data
* 數(shù)組對(duì)象
* @param left
* 左數(shù)組的第一個(gè)元素的索引
* @param center
* 左數(shù)組的最后一個(gè)元素的索引，center+1 是右數(shù)組第一個(gè)元素的索引
* @param right
* 右數(shù)組最后一個(gè)元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 臨時(shí)數(shù)組 int[] tmpArr = new int[data.length];
// 右數(shù)組第一個(gè)元素索引
int mid = center + 1;
// third 記錄臨時(shí)數(shù)組的索引
int third = left;
// 緩存左數(shù)組第一個(gè)元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組
if (data[left] <= data[mid]) { tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè) while 只會(huì)執(zhí)行其中一個(gè)）
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中
// （原 left-right 范圍的內(nèi)容被復(fù)制回原數(shù)組）
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}