快速排序算法实现文件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();
}
}
|
收藏
淘帖
踩
