归并排序自顶向下和自底向上分析及实现

自顶向下

归并排序分为两步：划分和归并

划分

排序思路：通过递归调用不断地将原始数组进行左右划分，直到划分成只有一个元素时停止，然后return,然后开始合并，其实排序的实现还是在merge里面实现的

 public void sort(int [] a){aux=new int[a.length];//一次性分配空间sort(a,0,a.length-1);//}public void sort(int a [],int low,int high)//排序{for(int i=low;i<=high;i++)System.out.print(a[i]+" ");System.out.println();if(high<=low)//划分得每个子数组只有一个元素了return;int mid=low+(high-low)/2;//再次确定划分得界限sort(a,low,mid);//将左半部分排序sort(a,mid+1,high);//将右边部分排序merge(a,low,mid,high);//开始合并System.out.print("merge:");for(int i=low;i<=high;i++)System.out.print(""+a[i]+" ");System.out.println();}

合并

进行合并的两个子数组本身已经是有序的了，在合并是采用一个额外的辅助数组先复制原数组的值，然后进行归并。先设置两个下标i,j,i指向左部第一个元素，j指向右部第一个元素，刚开始时第一个if和第二个if语句一般不满足条件，所以执行的是后面的两个if语句，以数据7 8 9 ‘ 1 2 3为例，右部的元素一直小于左部元素，因此前面取得就是 1 2 3,当右边的元素取完了，此时j>hi，所以第2个if语句条件满足，然后直接取左部元素7 8 9,最后的得到1 2 3 7 8 9。

public void merge(int a[],int low,int mid,int high)//归并{int i=low;int j=mid+1;for(int k=low;k<=high;k++)aux[k]=a[k];for(int k=low;k<=high;k++){if(i>mid) //左边已经用尽，开始取右半边元素a[k]=aux[j++];else if(j>high)//右边已经用尽，开始取左半边元素a[k]=aux[i++];else if(aux[j]<aux[i])//右半边元素小于左半边元素，取右半边元素---升序a[k]=aux[j++];else //左半边元素小于右半边元素，取左半边元素---升序a[k]=aux[i++];}}

从运行结果中可以看出，刚开始一直划分，直到划分到单个元素 16 15时停止，然后归并成15 16，然后再将14 13划分成单个元素14 13，然后归并成13 14，然后再归并成13 14 15 16，接着同样的步骤处理12 11 10 9…

自底向上

不再像自顶向下那样逐次划分，直接对长度为1 2 4 8 …的子数组进行合并

 public void sort_from_bottom_to_top(int a[]){int N=a.length;aux=new int[a.length];//一次性分配空间for(int sz=1;sz<N;sz=sz+sz)//sz为子数组的大小for(int lo=0;lo<N-sz;lo+=sz+sz)//lo为子数组索引merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));}

自底向上的归并排序会多次遍历整个数组，根据子数组的大小进行两两归并。子数组的大小sz的初始值为1，每次加倍。最后一个子数组的大小只有在数组的大小是sz的整数倍的时候才会等于sz,否则它会比sz小。

完整代码

public class test{int [] aux;//归并时所需的辅助数组public void sort(int [] a){aux=new int[a.length];//一次性分配空间sort_from_top_to_bottom(a,0,a.length-1);//}public void sort_from_top_to_bottom(int a [],int low,int high)//排序{for(int i=low;i<=high;i++)System.out.print(a[i]+" ");System.out.println();if(high<=low)//划分得每个子数组只有一个元素了return;int mid=low+(high-low)/2;//再次确定划分得界限sort_from_top_to_bottom(a,low,mid);//将左半部分排序sort_from_top_to_bottom(a,mid+1,high);//将右边部分排序merge(a,low,mid,high);//开始合并System.out.print("merge:");for(int i=low;i<=high;i++)System.out.print(""+a[i]+" ");System.out.println();}public void merge(int a[],int low,int mid,int high)//归并{int i=low;int j=mid+1;for(int k=low;k<=high;k++)aux[k]=a[k];for(int k=low;k<=high;k++){if(i>mid) //左边已经用尽，开始取右半边元素a[k]=aux[j++];else if(j>high)//右边已经用尽，开始取左半边元素a[k]=aux[i++];else if(aux[j]<aux[i])//右半边元素小于左半边元素，取右半边元素---升序a[k]=aux[j++];else //左半边元素小于右半边元素，取左半边元素---升序a[k]=aux[i++];}}public void sort_from_bottom_to_top(int a[])//自底向上{int N=a.length;aux=new int[a.length];//一次性分配空间for(int sz=1;sz<N;sz=sz+sz)//sz为子数组的大小for(int lo=0;lo<N-sz;lo+=sz+sz)//lo为子数组索引{merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));for(int k=lo;k<=Math.min(lo+sz+sz-1,N-1);k++)System.out.print(a[k]+" ");System.out.println();}}public static void main(String [] args){int [] a={16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};test t=new test();System.out.println("初始数组：");for(int i=0;i<16;i++)System.out.print(a[i]+" ");System.out.println();System.out.println("自顶向下实现：");t.sort(a);System.out.println("自底向上实现：");t.sort_from_bottom_to_top(a);for(int i=0;i<16;i++)System.out.print(a[i]+" ");}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！