问题描述

使用fork/join框架对大型浮点数数组排序排序

这个例子是《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()函数那里。但是我分析了一下，这个函数逻辑上没有问题，是不是因为处于多线程环境而导致出现问题呢？期待大家能够给予解惑，不甚感激！

解决方案

你的问题是什么呢？还是只是分享你发现了一个bug

解决方案二：

不好意思，因为发帖的时候突然有事，就没写完整。这里补上。

解决方案三：

不好意思，因为发帖的时候突然有事，就没写完整。这里补上。

解决方案四：

不好意思，因为发帖的时候突然有事，就没写完整。这里补上。