京东自营 618 + 国补 iPhone 历史最低价
Java Mergesort示例
Mergesort示例
实例源码：
源代码：
执行
执行中...
x
1
/*来自 N o w J a v a . c o m*/2
3
import static java.lang.System.out;4
5
6
class MergeImprove {7
8
9
private static final int CUTOFF = 7;10
11
12
13
private static void insertionSort(Comparable[] a, int lo, int hi) {14
15
for (int i = lo; i <= hi; i++)16
17
for (int j = i; j > lo && less(a[j], a[j-1]); j--)18
19
exch(a, j, j-1);20
21
}22
23
24
25
private static void exch(Comparable[] a, int i, int j) {26
27
Comparable swap = a[i];28
29
a[i] = a[j];30
31
a[j] = swap;32
33
}34
35
//n o w j a v a . c o m - 时 代 Java 提 供36
37
private static boolean less(Comparable v, Comparable w) {38
39
return v.compareTo(w) < 0;40
41
}42
43
44
45
public static boolean isSorted(Comparable[] a) {46
47
for (int i = 1; i < a.length; i++ )48
49
if (less(a[i], a[i-1]))50
51
return false;52
53
54
55
return true;56
57
}58
59
60
61
private static void merge(Comparable[] a, Comparable[] another, int lo, int mid, int hi) {62
63
int i = lo, j = mid + 1;64
65
66
67
for (int k = lo; k <= hi; k++) {68
69
if (i > mid)70
71
a[k] = another[j++];72
73
else if (j > hi)74
75
a[k] = another[i++];76
77
else if (less(another[j], another[i]))78
79
a[k] = another[j++];80
81
else82
83
a[k] = another[i++];84
85
}86
87
}88
89
90
91
private static void sort(Comparable[] a, Comparable[] another, int lo, int hi) {92
93
//improvement: use insertionSort for small subarray94
95
if (hi <= lo + CUTOFF) { 96
97
insertionSort(another, lo, hi);98
99
return;100
101
}102
103
104
105
int mid = lo + (hi - lo) / 2; //split the array in 2 parts106
107
108
109
sort(a, another, lo, mid); //left110
111
sort(a, another, mid+1, hi); //right112
113
114
115
//improvement: array already order116
117
if (!less(a[mid+1], a[mid])) {118
119
System.arraycopy(a, lo, another, lo, hi - lo + 1);120
121
return;122
123
}124
125
126
127
merge(a, another, lo, mid, hi);128
129
}130
131
132
133
public static void sort(Comparable[] a) {134
135
//improvement: clone() is a bit faster than the above loop (old merge)136
137
Comparable[] aux = a.clone();138
139
140
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java