# java归并排序

```package datastruct;

/**
* Created by Zephery on 2017/3/3.
*/
public class Solution {
public static void printArray(int[] arr, int i, int j) {
System.out.print("[");
for (int k = i; k < j; k++) {
System.out.print(arr[k] + ",");
}
System.out.print(arr[j] + "]");
}

private static void mergesort(int[] arr, int i, int j) {
int mid = 0;
if (i < j) {
mid = (i + j) / 2;
mergesort(arr, i, mid);
mergesort(arr, mid + 1, j);
merge(arr, i, mid, j);
}
}

private static void merge(int[] arr, int i, int mid, int j) {
System.out.print("Left:");
printArray(arr, i, mid);
System.out.println("Right:");
printArray(arr, mid + 1, j);
System.out.println();
int temp[] = new int[arr.length];
int l = i;
int r = j;
int m = mid + 1;
int k = l;
while (l <= mid && m <= r) {
if (arr[l] <= arr[m]) {
temp[k++] = arr[l++];
} else {
temp[k++] = arr[m++];
}
}
while (l <= mid) {
temp[k++] = arr[l++];
}
while (m <= r) {
temp[k++] = arr[m++];
}
for (int i1 = i; i1 <= j; i1++) {
arr[i1] = temp[i1];
}
System.out.print("After Merge:");
printArray(arr, i, j);
System.out.println();
}

public static void main(String args[]) {
int[] arr = {9, 4, 8, 3, 1, 2, 5};
System.out.print("Initial Array:");
printArray(arr, 0, arr.length - 1);
System.out.println();
mergesort(arr, 0, arr.length - 1);
}
}```
```Initial Array:[9,4,8,3,1,2,5]
Left:[9]Right:
[4]
After Merge:[4,9]
Left:[8]Right:
[3]
After Merge:[3,8]
Left:[4,9]Right:
[3,8]
After Merge:[3,4,8,9]
Left:[1]Right:
[2]
After Merge:[1,2]
Left:[1,2]Right:
[5]
After Merge:[1,2,5]
Left:[3,4,8,9]Right:
[1,2,5]
After Merge:[1,2,3,4,5,8,9]```

28 篇文章29 人订阅

0 条评论