多線(xiàn)程加速快排（java）

2019-11-06 06:11:44

字體：大中小

供稿：網(wǎng)友

1.快排的過(guò)程： a)設(shè)置兩個(gè)變量，分別指向數(shù)組的首尾，選擇一個(gè)標(biāo)志元素（一般是第一個(gè)元素） b)從后向前找比標(biāo)志元素小的值,從前向后找比標(biāo)志元素大的值，將小的移到低端，將大的移到高端，更新標(biāo)志元素的位置。 c)只要首尾兩個(gè)指針不相遇，就循環(huán)進(jìn)行這樣一次循環(huán)的結(jié)果是標(biāo)志元素左邊的都比它小，右邊的都比它大 d)將被標(biāo)志元素分開(kāi)的兩個(gè)數(shù)組再遞歸（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.多線(xiàn)程加速快排 a,b,c三步可以看成是一個(gè)小任務(wù)，將整個(gè)任務(wù)分成若干個(gè)小任務(wù)，分而治之。因?yàn)槊總€(gè)小任務(wù)之間有聯(lián)系，不能跟求值的多線(xiàn)程一樣，只要有個(gè)共享數(shù)據(jù)，將值相加。這里用Callable 接口（Callable 接口類(lèi)似于 Runnable），該接口可以帶返回值。

1）返回值的結(jié)構(gòu)為

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）實(shí)現(xiàn)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.普通快排與多線(xiàn)程加速快排的對(duì)比 測(cè)試類(lèi)：

public class Qsort { //創(chuàng)建線(xiàn)程池 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用來(lái)接收返回值 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 自動(dòng)生成的 catch 塊 e.printStackTrace(); } catch (ExecutionException e) { // TODO 自動(dòng)生成的 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)未加速的快排這里寫(xiě)圖片描述