-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
61 lines (50 loc) · 1.87 KB
/
Copy pathMergeSort.java
File metadata and controls
61 lines (50 loc) · 1.87 KB
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
package Sort;
import java.io.File;
import static FileUtil.ReadFileToArray.ReadFile;
import static java.lang.System.currentTimeMillis;
public class MergeSort extends Sort {
private static Comparable[] aux; // 归并所需的辅助数组
private static void sort(Comparable[] a) {
aux = new Comparable[a.length]; // 一次性分配空间
// sort(a, 0, a.length - 1);
MergeBu.sort(a);
}
// 自顶向下的归并排序
private static void sort(Comparable[] a, int lo, int hi) { // 将数组a[lo..hi]排序
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid); // 将左半边排序
sort(a, mid + 1, hi); // 将右半边排序
merge(a, lo, mid, hi); // 归并结果(代码见“原地归并的抽象方法”)
}
// 原地归并的抽象方法
public static void merge(Comparable[] a, int lo, int mid, int hi) {
// 将a[lo..mid] 和 a[mid+1..hi] 归并
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) // 将a[lo..hi]复制到aux[lo..hi]
aux[k] = a[k];
for (int k = lo; k <= hi; k++) {// 归并回到a[lo..hi]
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if
(less(aux[j], aux[i])) a[k] = aux[j++];
else
a[k] = aux[i++];
}
}
public static void main(String[] args) {
File file = new File("data.txt");
Comparable[] data = ReadFile(file);
long start = currentTimeMillis();
sort(data);
// merge(data,0,data.length / 2,data.length);
long end = currentTimeMillis();
for (Comparable intNumber: data) {
System.out.print(intNumber + " ");
}
System.out.println();
System.out.println(end - start + " ms");
}
}