排序算法之归并

2021-02-08 18:19

阅读:355

标签:数组   边界条件   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


评论


亲,登录后才可以留言!