文档章节

归并排序

AllenOR灵感
 AllenOR灵感
发布于 2017/09/10 01:00
字数 1071
阅读 1
收藏 0
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
        assert isSorted(a);
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo)
            return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

        assert isSorted(a, lo, mid);
        assert isSorted(a, mid + 1, hi);

        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                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++];
        }
        assert isSorted(a, lo, hi);
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i - 1]))
                return false;
        return true;
    }

上述时间复杂度为O(nlgn),空间复杂度为O(n),适用于排序大列表,基于分治法。
下列图片来展示长度16数组归并过程


归并结果轨迹
归并结果轨迹
调用轨迹
调用轨迹

归并排序有以下几点优化方法:

  1. 和快速排序一样,对于小数组可以使用插入排序或者选择排序,避免递归调用。
  2. 在merge()调用之前,可以判断一下a[mid]是否小于等于a[mid+1]。如果是的话那么就不用归并了,数组已经是有序的。原因很简单,既然两个子数组已经有序了,那么a[mid]是第一个子数组的最大值,a[mid+1]是第二个子数组的最小值。当a[mid]<=a[mid+1]时,数组整体有序。
  3. 为了节省将元素复制到辅助数组作用的时间,可以在递归调用的每个层次交换原始数组与辅助数组的角色。
  4. 在merge()方法中的归并过程需要判断i和j是否已经越界,即某半边已经用尽。可以用另一种方式,去掉检测是否某半边已经用尽的代码。具体步骤是将数组a[]的后半部分以降序的方式复制到aux[],然后从两端归并。对于数组{1,2,3}和{2,3,5},第一个子数组照常复制,第二个则从后往前复制,最终aux[]中的元素为{1,2,3,5,3,2}。这种方法的缺点是使得归并排序变为不稳定排序。代码实现如下:
    void merges(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        for (int k = lo; k <= mid; k++) {
            aux[k] = a[k];
        }
        for(int k = mid+1; k <= hi; k++) {
            aux[k] = a[hi-j+mid+1];
        }
        int i = lo, j = hi;
        for (int k = lo; k <= hi; k++) {
            if (less(aux[j], aux[i])) {
                a[k] = aux[j--];
            }
            else {
                a[k] = aux[i++];
            }
        }
    }

下面代码将上述前三种优化结合在一起

    public void sort(Comparable[] a) {
        Comparable[] aux = a.clone();
        //将aux放在第一位
        sort(aux,a,0,a.length-1);
        assert isSorted(a);
    }

    private void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
        if (hi <= lo + CUTOFF) {
            insertionSort(dst, lo, hi);
            return;
        }
        int mid = (lo + hi)/2;
        //对调
        sort(dst, src, lo, mid);
        sort(dst, src, mid+1, hi);
        
//      if (less(src[mid], src[mid+1])) {
//          for (int i = lo; i <= hi; i++) dst[i] = src[i];
//          return;
//      }
        
        //更快
        if (less(src[mid], src[mid+1])) {
            System.arraycopy(src, lo, dst, lo, hi-lo+1);
            return;
        }
        //对调
        merge(src, dst, lo, mid, hi);
    }

    private void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
        assert isSorted(src, lo, mid);
        assert isSorted(src, mid+1, hi);
        
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)                    dst[k] = src[j++];
            else if (j > hi)                dst[k] = src[i++];
            else if (less(src[i], src[j]))  dst[k] = src[i++];
            else                            dst[k] = src[j++];
        }
        assert isSorted(dst, lo, hi);
    }

    private void insertionSort(Comparable[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i++) {
            for (int j = i; j>lo && less(a[j], a[j-1]); j--) {
                exch(a, j, j-1);
            }
        }
    }

还有一种非递归版本:

    public void sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int len = 1; len < n; len *= 2) {
            //自底向上的归并排序,先前一个与后一个排,再前两个与后两个,再前四个与后四个...
            //要考虑到末尾元素不够的情况
            for (int lo = 0; lo < n - len; lo += len * 2) {
                int hi = Math.min(lo + len * 2 - 1, n - 1);
                int mid = lo + len - 1;
                merge(a, aux, lo, mid, hi);
            }
        }
    }

    public void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        for (int k = lo; k < hi; k++) {
            aux[k] = a[k];
        }

        int i = lo, j = mid + 1;
        for (int k = lo; k < hi; k++) {
            if (i > mid)
                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++];
        }
    }
1.jpg
1.jpg

本文转载自:http://www.jianshu.com/p/5bf417d05f19

下一篇: 二叉查找树
AllenOR灵感
粉丝 11
博文 2635
码字总数 83001
作品 0
程序员
私信 提问

暂无文章

【JVM学习】2.Java虚拟机运行时数据区

来源: 公众号: 猿人谷 这里我们先说句题外话,相信大家在面试中经常被问到介绍Java内存模型,我在面试别人时也会经常问这个问题。但是,往往都会令我比较尴尬,我还话音未落,面试者就会“...

物种起源-达尔文
23分钟前
2
0
dart datetime

var date = DateTime.now().toUtc(); //格式化输出 String timestamp = "${date.year.toString()}-${date.month.toString().padLeft(2, '0')}-${date.day.toString().padLeft(2, ......

zdglf
今天
20
0
如何在Linux中复制文档

在办公室里复印文档过去需要专门的员工与机器。如今,复制是电脑用户无需多加思考的任务。在电脑里复制数据是如此微不足道的事,以致于你还没有意识到复制就发生了,例如当拖动文档到外部硬盘...

老孟的Linux私房菜
今天
47
0
SpringBoot 集成MongoDB

一、MongoDB 简介 MongoDB 如今是最流行的 NoSQL 数据库,被广泛应用于各行各业中,很多创业公司数据库选型就直接使用了 MongoDB,但对于大部分公司,使用 MongoDB 的场景是做大规模数据查询...

zw965
今天
49
0
使用 Envoy 和 AdGuard Home 阻挡烦人的广告

> 原文链接:使用 Envoy 和 AdGuard Home 阻挡烦人的广告 通常我们使用网络时,宽带运营商会为我们分配一个 DNS 服务器。这个 DNS 通常是最快的,距离最近的服务器,但会有很多问题,比如: ...

米开朗基杨
今天
54
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部