multithreading合并排序

有人可以给我一个链接或提供multithreading合并排序的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 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

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

你在问题中说你想使用Executor – 我建议使用java.util.concurrent包，特别是Future接口。

资源：

• 归并
• 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 

Answer 4

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

您可以在此处使用测试版在Java6中使用此框架： http ： //gee.cs.oswego.edu/dl/concurrency-interest/