-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSortTask.java
More file actions
70 lines (59 loc) · 2 KB
/
Copy pathSortTask.java
File metadata and controls
70 lines (59 loc) · 2 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
62
63
64
65
66
67
68
69
70
package fork.join;
import java.util.Arrays;
import java.util.concurrent.RecursiveAction;
/**
* RecursiveAction 是 ForkJoinTask 的一个子类，它代表了一类最简单的 ForkJoinTask：不需要返回值，当子任务都执行完毕之后，不需要进行中间结果的组合。
* 如果我们从 RecursiveAction 开始继承，那么我们只需要重载 protected void compute() 方法。
* @author lzh
*
*/
public class SortTask extends RecursiveAction {
private static final long serialVersionUID = -6503381665358189219L;
final long[] array;
final int lo;
final int hi;
private int THRESHOLD = 30;
public SortTask(long[] array) {
this.array = array;
this.lo = 0;
this.hi = array.length - 1;
}
public SortTask(long[] array, int lo, int hi) {
this.array = array;
this.lo = lo;
this.hi = hi;
}
protected void compute() {
if (hi - lo < THRESHOLD)
sequentiallySort(array, lo, hi);
else {
int pivot = partition(array, lo, hi);
System.out.println("\npivot = " + pivot + ", low = " + lo + ", high = " + hi);
System.out.println("array" + Arrays.toString(array));
// coInvoke(new SortTask(array, lo, pivot - 1), new SortTask(array, pivot + 1, hi));
invokeAll(new SortTask(array,lo,pivot-1), new SortTask(array,pivot+1,hi));
}
}
private int partition(long[] array, int lo, int hi) {
long x = array[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (array[j] <= x) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, hi);
return i + 1;
}
private void swap(long[] array, int i, int j) {
if (i != j) {
long temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
private void sequentiallySort(long[] array, int lo, int hi) {
Arrays.sort(array, lo, hi + 1);
}
}