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 MergeBU(data);
s.show(data);
System.out.println(s.isSorted(data));
}
}
//希尔排序,自顶向下归并排序
class Merge extends BaseSort{
private Comparable[] data;
protected Merge(Comparable[] data) {
super(data.length);
this.data=data;
sort(this.data,0,data.length-1);
}
@Override
void sort(Comparable[] data, int lo, int hi) {
if(hi<=lo){
return;
}
int mid=lo+(hi-lo)/2;
sort(data,lo,mid);
sort(data,mid+1,hi);
merge(data,lo,mid,hi);
}
}
//自底向上归并排序
class MergeBU extends BaseSort{
private Comparable[] data;
protected MergeBU(Comparable[] data) {
super(data.length);
this.data=data;
int n=data.length;
for(int sz=1;sz<n;sz=sz+sz){
for(int lo=0;lo<n-sz;lo+=sz+sz){
merge(data,lo,lo+sz-1,Math.min(lo+sz+sz-1,n-1));
}
}
}
@Override
void sort(Comparable[] data, int lo, int hi) {
}
}
abstract class BaseSort {
abstract void sort(Comparable[] data,int lo,int hi);
protected Comparable[] aux;
protected BaseSort(int length){
aux=new Comparable[length];
}
//原地归并的抽象方法
public void merge(Comparable[] a, int lo,int mid,int hi){
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
aux[k]=a[k];
}
for(int k=lo;k<=hi;k++){
if(i>mid){
a[k]=aux[j++];
} else if(j>hi){
a[k]=aux[i++];
}else if(less(aux[j],aux[i])) {
a[k] = aux[j++];
}else{
a[k]=aux[i++];
}
}
}
//比较
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;
}
}

ITPub博客

归并排序

最新文章