-
Notifications
You must be signed in to change notification settings - Fork 1
/
merge_sort.java
44 lines (42 loc) · 1.25 KB
/
merge_sort.java
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
package ss;
//归并排序
public class merge_sort {
public static <T extends Comparable<? super T> >void run(T[] x){
run(x,(T[]) new Comparable[x.length],0,x.length-1);
}
private static <T extends Comparable<? super T> >
void run(T[] x, T[] objects, int i, int i1) {
if(i<i1){
int k=(i+i1)/2;
run(x,objects,i,k);
run(x,objects,k+1,i1);
//合并
merge(x,objects,i,k,k+1,i1);
}
}
private static <T extends Comparable<? super T> >
void merge(T[] x, T[] objects, int a1, int a2, int b1, int b2) {
int i=a1,j=b2;
int temp=a1;
//合并两个数组
while (a1<=a2&&b1<=b2){
if(x[a1].compareTo(x[b1])<0)
objects[temp++]=x[a1++];
else
objects[temp++]=x[b1++];
}
//剩下的全部直接复制到objects
if(a1>a2)
while (b1<=b2)
objects[temp++]=x[b1++];
else if(b1>b2)
while (a1<=a2)
objects[temp++]=x[a1++];
//复制回去
for(;i<=j;i++)
x[i]= objects[i];
}
public static void main(String[] x){
tools.testyuanzhisort(merge_sort::run,"归并排序");
}
}