多线程加速快排（java）

2019-11-06 06:11:44

字体：大中小

来源：转载

供稿：网友

1.快排的过程： a)设置两个变量，分别指向数组的首尾，选择一个标志元素（一般是第一个元素） b)从后向前找比标志元素小的值,从前向后找比标志元素大的值，将小的移到低端，将大的移到高端，更新标志元素的位置。 c)只要首尾两个指针不相遇，就循环进行这样一次循环的结果是标志元素左边的都比它小，右边的都比它大 d)将被标志元素分开的两个数组再递归（a,b,c） 2.快排代码

class quicksort{ public void sort(int left,int right,int str[]) { int i,j,pos; if(left>=right) { return; } i=left; j=right; pos=str[i]; while(i<j) { while(i<j && pos<=str[j]) { j--; } if(i<j) { str[i]=str[j]; } while(i<j && pos>=str[i]) { i++; } if(i<j) { str[j] = str[i]; } str[i]=pos; sort(left,i-1,str); sort(i+1,right,str); } }}

3.多线程加速快排 a,b,c三步可以看成是一个小任务，将整个任务分成若干个小任务，分而治之。因为每个小任务之间有联系，不能跟求值的多线程一样，只要有个共享数据，将值相加。这里用Callable 接口（Callable 接口类似于 Runnable），该接口可以带返回值。

1）返回值的结构为

class temp{ PRivate int left=0; private int right=0; private int middle=0; public temp(int left, int right, int middle) { this.left = left; this.right = right; this.middle = middle; } public int getLeft() { return left; } public int getRight() { return right; } public int getMiddle() { return middle; } public boolean cmpLeftMiddle() { return left<middle-1; } public boolean cmpMiddleRight() { return middle+1<right; }}

2）实现Callable 接口

class myThread implements Callable<temp>{ private int left; private int right; private int middle; private int str[]; public myThread(int left, int right, int str[]) { this.left=left; this.right=right; this.str=str; } public temp call() { onesort(); return new temp(left,right,middle); } public void onesort() { int i,j,pos; if(left>=right) { return; } i=left; j=right; pos=str[i]; while(i<j) { while(i<j && pos<=str[j]) { j--; } if(i<j) { str[i]=str[j]; } while(i<j && pos>=str[i]) { i++; } if(i<j) { str[j] = str[i]; } str[i]=pos; } middle = i; }}

4.普通快排与多线程加速快排的对比 测试类：

public class Qsort { //创建线程池 ExecutorService pool = Executors.newFixedThreadPool(6); private int[] str=null; public Qsort(int str[]) { this.str = str; sort(0,str.length-1); } //分治 public void sort(int begin, int end) { //Future用来接收返回值 Future<temp> future = pool.submit(new myThread(begin, end, str)); try { if(future.get().cmpLeftMiddle()) { sort(future.get().getLeft(),future.get().getMiddle()-1); } if(future.get().cmpMiddleRight()) { sort(future.get().getMiddle()+1,future.get().getRight()); } } catch (InterruptedException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); } catch (ExecutionException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); } } public static void main(String[] args) { int a[] = new int[1024]; for(int i=0;i<1024; i++) { a[i] = (int)(Math.random()*100); System.out.print(a[i]+" "); } System.out.println(); long star = System.currentTimeMillis(); new Qsort(a); // new quicksort().sort(0, a.length-1, a); long end = System.currentTimeMillis(); for(int i=0; i<a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); System.out.println(end-star); }}

1)未加速的快排这里写图片描述