1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
package merge;
/**
* @author 陶波利
*/
public class MergeSort {
private static void merge(int[] arr, int l, int m, int r) {
int leftArraySize = m - l + 1;
// r - (m + 1) + 1
int rightArraySize = r - m;
// temp array
int[] leftTempArray = new int[leftArraySize];
int[] rightTempArray = new int[rightArraySize];
// 把 arr 中的数据拷入两个 temp 数组
for (int i = 0; i < leftArraySize; i++) {
leftTempArray[i] = arr[l + i];
}
for (int i = 0; i < rightArraySize; i++) {
rightTempArray[i] = arr[m + 1 + i];
}
// 两个 temp 数组的索引
int i = 0, j = 0;
// arr 数组的索引
int k = l;
// 将 temp 数组的数据按顺序填入 arr
while (i < leftArraySize && j < rightArraySize) {
if (leftTempArray[i] <= rightTempArray[j]) {
arr[k] = leftTempArray[i];
i++;
} else {
arr[k] = rightTempArray[j];
j++;
}
k++;
}
while (i < leftArraySize) {
arr[k] = leftTempArray[i];
i++;
k++;
}
while (j < rightArraySize) {
arr[k] = rightTempArray[j];
j++;
k++;
}
}
public static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
public static void main(String[] args) {
int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
mergeSort(arr, 0, arr.length - 1);
StringBuilder builder = new StringBuilder();
builder.append("Sorted array:\n[");
for (int i = 0; i < arr.length; i++) {
builder.append(arr[i]);
if (i != arr.length - 1) {
builder.append(" ,");
}
}
builder.append("]");
System.out.println(builder.toString());
}
}
|