这个例子是《java7 编程高级进阶》一书第474页的例子。代码如下:
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveAction;
public class Daemon {
private static ForkJoinPool threadPool;
private static final int THRESHOLD=16;
private static void sort(Comparable[] objectArray){
Comparable[] destArray=new Comparable[objectArray.length];
threadPool.invoke(new SortTask(objectArray,destArray,0,objectArray.length-1));
//Future future=threadPool.submit(new SortTask(objectArray,destArray,0,objectArray.length-1));
}
static class SortTask extends RecursiveAction{
private Comparable[] sourceArray;
private Comparable[] destArray;
private int lowerIndex,upperIndex;
public SortTask(Comparable[] sourceArray,Comparable[] destArray,int lowerIndex,int upperIndex){
this.sourceArray=sourceArray;
this.destArray=destArray;
this.lowerIndex=lowerIndex;
this.upperIndex=upperIndex;
}
@Override
protected void compute(){
if(upperIndex-lowerIndex<THRESHOLD){
insertionSort(sourceArray,lowerIndex,upperIndex);
return;
}
int midIndex=(lowerIndex+upperIndex)>>>1;//无符号右移
SortTask leftTask=new SortTask(sourceArray,destArray,lowerIndex,midIndex);
SortTask rightTask=new SortTask(sourceArray,destArray,midIndex+1,upperIndex);
leftTask.fork();
rightTask.fork();
leftTask.join();
rightTask.join();
merge(sourceArray,destArray,lowerIndex,midIndex,upperIndex);
}
}//类结束
private static void merge(Comparable[] sourceArray,Comparable[] destArray,int lowerIndex,int midIndex,int upperIndex){
if(sourceArray[midIndex].compareTo(sourceArray[midIndex+1])<=0){
return;
}
System.arraycopy(sourceArray, lowerIndex, destArray, lowerIndex, midIndex-lowerIndex+1);
int i=lowerIndex;
int j=midIndex;
int k=lowerIndex;
while(k<j && j<=upperIndex){
if(destArray[i].compareTo(sourceArray[j])<=0){
sourceArray[k++]=destArray[i++];
}else{
sourceArray[k++]=sourceArray[j++];
}
}
System.arraycopy(destArray, i, sourceArray, k, j-k);
}
private static void insertionSort(Comparable[] objectArray,int lowerIndex,int upperIndex){
for(int i=lowerIndex+1;i<=upperIndex;i++){
int j=i;
Comparable tempObject=objectArray[j];
while(j>lowerIndex && tempObject.compareTo(objectArray[j-1])<0){
objectArray[j]=objectArray[j-1];
--j;
}
objectArray[j]=tempObject;
}
}
public static Double[] createRandomData(int length){
Double[] data=new Double[length];
for(int i=0;i<data.length;i++){
data[i]=length*Math.random();
}
return data;
}
public static void main(String[] args) throws InterruptedException {
int processors=Runtime.getRuntime().availableProcessors();
System.out.println("Number of processors: "+processors);
threadPool=new ForkJoinPool(processors);
Double[] data=createRandomData(30);
System.out.println("Original unsorted data: ");
for (Double d: data){
System.out.printf("%3.2f ",d);
}
sort(data);
System.out.println("\nSorted Array: ");
for(Double d:data){
System.out.printf("%3.2f ", d);
}
}
}
但是输出结果有问题:
为了减少输出,我设定待排序数量为30.可以看到,排序后的数组中前15个是有序的,后15个也是有序的。但是整体而言就不是有序的了。所以我猜想问题就出现在合并那一步,即merge()函数那里。但是我分析了一下,这个函数逻辑上没有问题,是不是因为处于多线程环境而导致出现问题呢?期待大家能够给予解惑,不甚感激!