-
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 Quick(data);
-
-
s.show(data);
-
-
System.out.println(s.isSorted(data));
-
}
-
}
-
-
-
-
class Quick extends BaseSort{
-
public Quick(Comparable[] data){
-
sort(data,0,data.length-1);
-
}
-
-
@Override
-
void sort(Comparable[] data, int lo, int hi) {
-
if(hi<=lo){
-
return;
-
}
-
int j=partition(data,lo,hi);
-
sort(data,lo,j-1);
-
sort(data,j+1,hi);
-
}
-
-
private int partition(Comparable[] data, int lo, int hi) {
-
int i=lo,j=hi+1;
-
Comparable v=data[lo];
-
while(true){
-
while(less(data[++i],v)){
-
if(i==hi)
-
break;
-
}
-
while(less(v,data[--j])){
-
break;
-
}
-
if(i>=j){
-
break;
-
}
-
exch(data,i,j);
-
}
-
exch(data,lo,j);
-
return j;
-
}
-
}
-
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;
-
}
- }
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29254281/viewspace-2125289/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
