多線程加速快排（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)未加速的快排這里寫圖片描述