排序算法之归并

标签：数组   边界条件   i++   算法   com   lse   private   归并排序   初始   

归并排序

归并算法是在分治的思想下，将数组递归的分为两半，分别排序后，再归并成
整个数组。所谓分治，即分而治之。

优点：对于长度为 N 的数组，无论规模多大，排序所需时间总和 NlogN 成正比。
缺点：排序所需额外空间和 N 成正比。

注意：归并排序的核心不是交换数据。

1. 自顶向下的归并排序

package mysort;

//归并类
class Merge {
    //定义一个临时辅助数组
    private static Comparable[] aux;
    //对外提供排序方法
    public static void sort(Comparable[] a){
        //初始化辅助数组(注意不要减1)
        aux=new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    //内部真正起到排序作用的方法
    private static void sort(Comparable[] a,int lo,int hi){
        //边界条件
        if(himid) {
                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++];
            }
        }
    }
    //此方法用于判断前者是否小于后者
    private static boolean less(Comparable m, Comparable n){
        return m.compareTo(n)

2. 自底向上的归并排序

自顶向下的归并算法过程是将数组递归到底层，进行两两比较，再向上合并。
而自底向上的归并排序则直接将数组元素进行比较，然后两两归并，四四归并，八八归并，直到合成一个数组。

private static void sort(Comparable[] a){
        //sz为子数组的大小：1、2、4、8、16...
        for(int sz=1;sz

3. 两者联系

• 当数组长度为2的幂时，两者本质上相同，仅在访问顺序上相反。
• 自底向上的方式较适合链表，不需要创建新节点。而自顶向下，需要创建一条新链表。
• 自顶向下用到递归，自底向上没有用递归。

排序算法之归并

标签：数组   边界条件   i++   算法   com   lse   private   归并排序   初始   

原文地址：https://www.cnblogs.com/juzhuxiaozhu/p/12770834.html