多线程归并排序

Question

有人可以给我一个链接或为我提供多线程合并排序的java代码吗？

最好使用执行器！

非常感谢！

Answer 1

这是我使用 2 个线程的 MergeSort 版本，它可以轻松扩展到 n 个线程（只需将原始数组拆分为 n 个子数组）。对于 1000 万个数字，它比单线程的速度快约 25%。

import java.util.Random;

public class MergeSortThreaded {

    public static void finalMerge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int i=0; 
        int j=0; 
        int r=0;
        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                result[r]=a[i];
                i++;
                r++;
            } else {
                result[r]=b[j];
                j++;
                r++;
            }
            if (i==a.length) {
                while (j<b.length) {
                    result[r]=b[j];
                    r++;
                    j++;
                }
            }
            if (j==b.length) {
                while (i<a.length) {
                    result[r]=a[i];
                    r++;
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Random rand = new Random();
        int[] original = new int[10000000];
        for (int i=0; i<original.length; i++) {
            original[i] = rand.nextInt(1000);
        }

        long startTime = System.currentTimeMillis();
        int[] subArr1 = new int[original.length/2];
        int[] subArr2 = new int[original.length - original.length/2];
        System.arraycopy(original, 0, subArr1, 0, original.length/2);
        System.arraycopy(original, original.length/2, subArr2, 0, original.length - original.length/2);

        Worker runner1 = new Worker(subArr1);
        Worker runner2 = new Worker(subArr2);
        runner1.start();
        runner2.start();
        runner1.join();
        runner2.join();
        finalMerge (runner1.getInternal(), runner2.getInternal());
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("2-thread MergeSort takes: " + (float)elapsedTime/1000 + " seconds");
    }

}

class Worker extends Thread {
    private int[] internal;

    public int[] getInternal() {
        return internal;
    }

    public void mergeSort(int[] array) {
        if (array.length > 1) {
            int[] left = leftHalf(array);
            int[] right = rightHalf(array);

            mergeSort(left);
            mergeSort(right);

            merge(array, left, right);
        }
    }

    public int[] leftHalf(int[] array) {
        int size1 = array.length / 2;
        int[] left = new int[size1];
        for (int i = 0; i < size1; i++) {
            left[i] = array[i];
        }
        return left;
    }

    public int[] rightHalf(int[] array) {
        int size1 = array.length / 2;
        int size2 = array.length - size1;
        int[] right = new int[size2];
        for (int i = 0; i < size2; i++) {
            right[i] = array[i + size1];
        }
        return right;
    }

    public void merge(int[] result, int[] left, int[] right) {
        int i1 = 0;   
        int i2 = 0;   

        for (int i = 0; i < result.length; i++) {
            if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
                result[i] = left[i1];   
                i1++;
            } else {
                result[i] = right[i2];   
                i2++;
            }
        }
    }

    Worker(int[] arr) {
        internal = arr;
    }

    public void run() {
        mergeSort(internal);
    }
}

Answer 2

我建议多线程合并排序与常规合并排序非常相似，但是，当递归调用列表的每一半的合并排序时，请设置算法以在新线程中调用每个合并。然后，您可以等到两个线程都完成，然后将两个列表合并在一起，然后返回。简单的！

您在问题中说您想使用 Executor - 我建议 java.util.concurrent 包可用于此目的，特别是 未来界面。

资源：

• Mergesort
• Java 线程
• 使用 J2SE 5.0 进行并发编程

Answer 3

我尝试只使用 join 方法。它基本上为每个子问题生成线程，并使用 join 等待生成的线程完成。

让我知道您的意见。

   package com.kayan.dsAlgo;

   public class MergeSorter implements Runnable{


private int[] arr;
private int Size;
private int left;
private int right;
private int[] resultArr ;

public MergeSorter(int[] arr, int i, int j) {
    this.arr = arr;
    this.Size = arr.length;
    //this.resultArr = new int[j-i+1];
    this.left  = i;
    this.right = j;
}



@Override
public void run() {

    System.out.println("Starting new thread left :"+this.left+" right "+this.right);

    sort();

}

public static void main(String[] args) {

    int arr[] ={3,6,4,2,1,10} ;
    MergeSorter mr = new MergeSorter(arr,0,arr.length-1);

    Thread t = new Thread(mr);
    t.start();
    //mr.run();

try {
        t.join();
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

for (int i :mr.resultArr)
        System.out.print(i+" ");
    //int res[]= mr.sort(0,arr.length-1);

}






private void sort() {

    if(left==right && left >=0 )
    {
         this.resultArr = new int[]{arr[left]};
         return;
    }
    if(left>right) return;

    int rightLimit = this.left+(right-left)/2;
    //int leftArr[] = sort( left,rightLimit );

    MergeSorter mleft = new MergeSorter(arr,left,rightLimit);
    Thread t1 = new Thread(mleft);
    t1.start();

     int leftlimit = 1 + rightLimit;            
     //int rightArr[] = sort(leftlimit , right);

     MergeSorter mright= new MergeSorter(arr,leftlimit,right);
     Thread t2 = new Thread(mright);
      t2.start();


       try {
        t1.join();
        t2.join();
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

      merge(mleft.resultArr,mright.resultArr);



}



private  int[] merge(int[] left, int[] right) {
     resultArr = new int[left.length+right.length];

    int r=0;
    int i=0;
    int j=0;
    while(i<left.length && j <right.length )
    {   
        if( i<left.length && j<right.length && left[i] < right[j] )
            resultArr[r++] = left[i++];

        else if( j<right.length && i<left.length && right[j] < left[i])
            resultArr[r++] = right[j++];
    }   


    while(i<left.length)
    {
        resultArr[r++] = left[i++];
    }        

    while(j<right.length)
    {
        resultArr[r++] = right[j++];
    }        


    //System.out.println("resultArr "+resultArr);
    return resultArr;
}



}

Answer 4

下面是一个使用 Java7 ForkJoin 框架的示例：
http://www.ibm.com/developerworks/java/library/ j-jtp03048.html

您可以通过使用此处的测试版本在 Java6 中使用此框架：
http://gee.cs.oswego.edu/dl/concurrency-interest/< /a>