黑马程序员技术交流社区

标题: 多线程实现快速排序 [打印本页]

---

作者: HM代景康    时间: 2013-10-23 21:29
标题: 多线程实现快速排序
快速排序算法实现文件QuickSort.java

　　package quick.sort;

　　import java.util.concurrent.Callable;

　　import java.util.concurrent.locks.Lock;

　　import java.util.concurrent.locks.ReentrantLock;

　　public class QuickSort implements Callable<Point>{

　　private int[] array;

　　private final int start;

　　private final int end;

　　private int middle;

　　Lock lock = new ReentrantLock();

　　public QuickSort(int start,int end,int[] array){

　　this.start = start;

　　this.end = end;

　　this.array = array;

　　}

　　@Override

　　public Point call() {

　　/*进行排序*/

　　quickSort();

　　return new Point(start,end,middle);

　　}

　　public void quickSort(){

　　int head,tail;

　　head = start;

　　tail = end + 1;

　　while(true){

　　/*找到一个比head大的*/

　　do{

　　head++;

　　}while(!(array[head] >= array[start] || head == end));

　　/*找到一个比head小的*/

　　do{

　　tail--;

　　}while(!(array[start] >= array[tail] || tail == start));

　　if(head < tail)

　　swap(head,tail);

　　else

　　break;

　　}

　　swap(start,tail);

　　middle = tail;

　　}

　　public void swap(int a,int b){

　　int temp = 0;

　　temp = array[a];

　　array[a] = array[b];

　　array[b] = temp;

　　}

　　}

　　class Point{

　　private int start;

　　private int end;

　　private int middle;

　　public Point(int start,int end,int middle){

　　this.start = start;

　　this.end = end;

　　this.middle = middle;

　　}

　　public int getStart(){

　　return start;

　　}

　　public int getEnd(){

　　return end;

　　}

　　public int getMiddle(){

　　return middle;

　　}

　　public boolean compareStartMiddle(){

　　return start < middle - 1;

　　}

　　public boolean compareMiddleEnd(){

　　return middle + 1 < end;

　　}

　　}

创建线程文件：ThreadExecutor.java

　　package quick.sort;

　　import java.util.concurrent.ExecutionException;

　　import java.util.concurrent.ExecutorService;

　　import java.util.concurrent.Executors;

　　import java.util.concurrent.Future;

　　public class ThreadExecutor {

　　public static ExecutorService exec = Executors.newCachedThreadPool();

　　private int[] array;

　　public ThreadExecutor(int[] array){

　　this.array = array;

　　createThread(0,array.length - 1);

　　}

　　public void createThread(int start,int end){

　　Future<Point> future = exec.submit((new QuickSort(start,end,array)));

　　try {

　　System.out.println(future.get().getMiddle());

　　if(future.get().compareStartMiddle())

　　createThread(future.get().getStart(),future.get().getMiddle() - 1);

　　if(future.get().compareMiddleEnd())

　　createThread(future.get().getMiddle() + 1,future.get().getEnd());

　　} catch (InterruptedException e) {

　　// TODO Auto-generated catch block

　　e.printStackTrace();

　　} catch (ExecutionException e) {

　　// TODO Auto-generated catch block

　　e.printStackTrace();

　　}

　　}

　　public void print(){

　　for(int g : array)

　　System.out.print(g + " ");

　　}

　　public static void main(String[] args){

　　int[] array = {10,9,8,7,5,6,4,3,2,1};

　　ThreadExecutor tx = new ThreadExecutor(array);

　　tx.print();

　　}

　　}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2