归并排序

九大排序算法之归并排序自顶向下的归并排序//归并排序自顶向下的归并排序。 //分治思想 //递归的先将两个数组分成两半分别排序然后将结果归并起来 //时间复杂度NlogN,空间复杂度N public class Merge { public static Comparable[] aux; public static void sort(Comparable[] a) { auxnew Comparable[a.length]; sort(a,0,a.length-1); } public static void sort(Comparable[] a,int lo,int hi) { if(hilo) return; int midlo(hi-lo)/2; sort(a,lo,mid);//将左半边排序 sort(a,mid1,hi);//将右半边排序 merge(a,lo,mid,hi);//归并 } public static void merge(Comparable[] a,int lo,int mid,int hi) { int ilo,jmid1; for(int klo;khi;k) { aux[k]a[k]; } for(int klo;khi;k) { if(imid)a[k]aux[j]; else if(jhi)a[k]aux[i]; else if(less(aux[j],aux[i]))a[k]aux[j]; else a[k]aux[i]; } } private static boolean less(Comparable v,Comparable w) { return v.compareTo(w)0; } public static boolean isSorted(Comparable[] a) { for(int i1;ia.length;i) { if(less(a[i],a[i-1])) return false; } return true; } private static void show(Comparable[] a) { for(int i0;ia.length;i) { System.out.print(a[i] ); } System.out.println(); } public static void main(String[] args) { // TODO Auto-generated method stub String[] a {3,2,4,5,7}; sort(a); assert isSorted(a); show(a); } }自底向上的归并排序//迭代归并排序自底向上 //先归并微型数组再归并得到的子数组 //首先两两归并再四四归并。。。。。。 public class MergeBU { public static Comparable[] aux;//归并所需的辅助数组 public static void sort(Comparable[] a) { int Na.length; auxnew Comparable[N]; for(int sz1;szN;szszsz) {//sz子数组大小 for(int lo0;loN-sz;loszsz) { merge(a,lo,losz-1,Math.min(loszsz-1, N-1)); } } } public static void merge(Comparable[] a,int lo,int mid,int hi) { int ilo,jmid1; for(int klo;khi;k) { aux[k]a[k]; } for(int klo;khi;k) { if(imid)a[k]aux[j]; else if(jhi)a[k]aux[i]; else if(less(aux[j],aux[i]))a[k]aux[j]; else a[k]aux[i]; } } private static boolean less(Comparable v,Comparable w) { return v.compareTo(w)0; } public static boolean isSorted(Comparable[] a) { for(int i1;ia.length;i) { if(less(a[i],a[i-1])) return false; } return true; } private static void show(Comparable[] a) { for(int i0;ia.length;i) { System.out.print(a[i] ); } System.out.println(); } public static void main(String[] args) { // TODO Auto-generated method stub String[] a {3,2,4,5,7}; sort(a); assert isSorted(a); show(a); } }