package test;
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
System.out.println("排序前：");
printArr(arr);
sort(arr);
System.out.println("排序后：");
printArr(arr);
}
private static void sort(int[] arr) {
int[] tmp = new int[arr.length];
sort(arr, 0, arr.length - 1, tmp);
}
private static void sort(int[] arr, int left, int right, int[] tmp) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid, tmp);
sort(arr, mid + 1, right, tmp);
merge(arr, left, mid, right, tmp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] tmp) {
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
tmp[t++] = arr[i];
i++;
} else {
tmp[t++] = arr[j];
j++;
}
}
for (; i <= mid; i++) {
tmp[t++] = arr[i];
}
for (; j <= right; j++) {
tmp[t++] = arr[j];
}
// 将tmp前t个数据拷贝到arr的Left至right的位置中；
System.arraycopy(tmp, 0, arr, left, t);
printArr(arr);
// 清空；
for (i = 0; i < tmp.length; i++) {
tmp[i] = 0;
}
}
/**
* 打印；
*
* @param arr
*/
private static void printArr(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
运行
结果