-
public class Sort{
-
public static void main(String[] args){
-
Integer[] data={100,20,21,28,22,26,80,33,3,2,9,8,7,10,77,66,99,96,91,94};
-
BaseSort s=new Quick3Way(data);
-
-
s.show(data);
-
-
System.out.println(s.isSorted(data));
-
}
-
}
-
-
-
-
class Quick3Way extends BaseSort{
-
public Quick3Way(Comparable[] data){
-
sort(data,0,data.length-1);
-
}
-
-
@Override
-
void sort(Comparable[] data, int lo, int hi) {
-
if(hi<=lo){
-
return;
-
}
-
int lt=lo,i=lo+1,gt=hi;
-
Comparable v=data[lo];
-
while(i<=gt){
-
int cmp=data[i].compareTo(v);
-
if(cmp<0) {
-
exch(data, lt++, i++);
-
}else if(cmp>0){
-
exch(data,i,gt--);
-
}else{
-
i++;
-
}
-
}
-
sort(data,lo,lt-1);
-
sort(data,gt+1,hi);
-
}
-
}
-
abstract class BaseSort {
-
abstract void sort(Comparable[] data,int lo,int hi);
-
-
//比较
-
public boolean less(Comparable v,Comparable w){
-
return v.compareTo(w)<0;
-
}
-
-
//打印
-
public void show(Comparable[] data){
-
for(int i=0;i<data.length;i++){
-
System.out.print(data[i]+" ");
-
}
-
System.out.println("");
-
}
-
-
//验证
-
public boolean isSorted(Comparable[] data){
-
for(int i=1;i< data.length;i++){
-
if(less(data[i],data[i-1]) )
-
return false;
-
}
-
return true;
-
}
-
-
//交换
-
public void exch(Comparable[] data,int i,int j){
-
Comparable t=data[i];
-
data[i]=data[j];
-
data[j]=t;
-
}
- }
if(hi<=lo){ return; }小数组可以改为插入排序。
int M=5; if(hi<=lo+M){ Insertion.sort(data,lo,hi); return; }
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29254281/viewspace-2125329/ ，如需转载，请注明出处，否则将追究法律责任。
上一篇：
二叉堆优先队列
请登录后发表评论
登录
全部评论
