希尔排序
希尔排序算法实际上是一种特殊的插入排序,由DL.Shell于1959年提出而得名。
算法思想:希尔排序使数组中任意间隔为h的元素都是有序的,这些数组称为h有序数组,对于每个h,按插入排序进行排序。
算法实现:
public static void sort(int [] array){ int h=1; while(h<array.length/3) h=3*h+1; while(h>=1){ for(int i=h;i<array.length;i++){ for(int j=i;j>=h&&array[j]<array[j-h];j=j-h){ int temp=array[j]; array[j]=array[j-h]; array[j-h]=temp; } } h=h/3; }
分析:
然后执行h=h/3=1,即按插入排序对整个数组进行排序。此时倒置的元素很少,插入排序的效率大大提高。
归并排序
算法思想:基于分治的思想,将待排序的数组(递归的)分成两半,对这两部分分别排序,然后将结果归并起来。
算法实现(自顶向下递归实现):
public static int [] aux; public static void merge(int []array,int lo,int mid,int hi){//归并操作 int i=lo,j=mid+1; for(int k=lo;k<=hi;k++){ aux[k]=array[k]; } for(int k=lo;k<=hi;k++){ if(i>mid) array[k]=aux[j++]; else if(j>hi) array[k]=aux[i++]; else if(aux[j]<aux[i]) array[k]=aux[j++]; else array[k]=aux[i++]; } } public static void sort(int []array){ aux=new int[array.length]; sort(array,0,array.length-1); } public static void sort(int []array,int lo,int hi){ if(hi<=lo) return ; int mid=lo+(hi-lo)/2; sort(array,lo,mid); sort(array,mid+1,hi); merge(array,lo,mid,hi); }
自底向上:
public static int [] aux; public static void merge(int []array,int lo,int mid,int hi){ int i=lo,j=mid+1; for(int k=lo;k<=hi;k++){ aux[k]=array[k]; } for(int k=lo;k<=hi;k++){ if(i>mid) array[k]=aux[j++]; else if(j>hi) array[k]=aux[i++]; else if(aux[j]<aux[i]) array[k]=aux[j++]; else array[k]=aux[i++]; } } public static void sort(int []array){ aux=new int[array.length]; for(int i=1;i<array.length;i=2*i){//两两进行合并 for(int lo=0;lo<array.length-i;lo=lo+2*i){ merge(array,lo,lo+i-1,Math.min(lo+2*i-1, array.length-1)); } } }
时间复杂度为 Nlg(N)