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
| public class MergeSort {
int data[];
MergeSort(int[] data){
this.data = data;
}
public void sort(int l,int r){
int[] tmp = new int[r-l+1];
sort0(l,r,tmp,0,r-l);
}
public void sort0(int l,int r,int[] tmp,int lt,int rt){
if(l<r){
int mid = (l+r)/2;
sort0(l,mid,tmp,lt,mid-l+lt);
sort0(mid+1,r,tmp,mid+1-l+lt,rt);
merge(l,r,tmp,lt,rt);
for (int i = l,t=lt; i <=r ; i++,t++) {
data[i]=tmp[t];
}
}
System.out.println(l+" "+r+" "+Arrays.toString(data));
}
private void merge(int l, int r,int[] tmp,int lt,int rt) {
int r1 = (l+r)/2;
int l2 = r1+1;
while (l<=r1&&l2<=r){
if(data[l]<=data[l2]){
tmp[lt]=data[l];
l++;
}else {
tmp[lt]=data[l2];
l2++;
}
lt++;
}
if(l>r1){
l=l2;
}
while (lt<=rt){
tmp[lt]=data[l];
lt++;
l++;
}
}
public static void main(String[] args) {
int[] data = new int[]{8,6,9,2,5,1,7,10,3,4};
MergeSort ms = new MergeSort(data);
ms.sort(0,data.length-1);
System.out.println(Arrays.toString(data));
}
}
|
微信打赏