majishushu
灿夏
采纳率100%
2018-07-28 02:59 阅读 711
已采纳

关于java归并排序的问题

5

下面是代码 我的问题是 Merge方法里面的那四种判断是根据什么来的?j>hi是怎么回事,

 public class Merge {

    private static Comparable[] b;

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

    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

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

            if (i > mid) {
                a[k] = b[j++];
            } else if (j > hi) {
                a[k] = b[i++];
            } else if (less(b[i], b[j])) {
                a[k] = b[i++];
            } else {
                a[k] = b[j++];
            }
        }
    }

    /**
     * 自顶向下和自底向上
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        b = new Comparable[a.length];
        // 自顶向下
        sort(a, 0, a.length - 1);

        //自底向上
//        for (int i = 1; i < a.length; i++) {
//            for (int lo = 0; lo < a.length - i; lo += i + i) {
//                merge(a, lo, lo + i - 1, Math.min(lo + i + i - 1, a.length - 1));
//            }
//        }
    }

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

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Integer[] a = new Integer[10];
        for (int i = 0; i < 10; i++) {
            a[i] = (int) (Math.random() * 10 + 1);
        }
        show(a);
        sort(a);
        show(a);
    }

}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    caozhy 从今以后生命中的每一秒都属于我爱的人 2018-07-28 04:13
     int lo, int mid, int hi
    分别是待归并的两部分数组的起始位置,第一个是lo~mid,第二个是mid+1~hi
    
            int i = lo;
            int j = mid + 1;
    开始的时候,i和j分别指向两部分数组的开始位置
    
    for (int k = lo; k < hi + 1; k++) {
                b[k] = a[k];
            }
    首先复制一份拷贝到b里面,而原来的a数组的相应位置则保存排序后的结果
    
    for (int k = lo; k < hi + 1; k++) {
    
                if (i > mid) { //i > mid说明第一个数组中的数据都已经插入到a里面了,而第二个数组是有序的,所以照着复制就可以
                    a[k] = b[j++];
                } else if (j > hi) { //j>h说明第二个数组已经都插入进去了,而第一个数组是有序的,所以照着复制
                    a[k] = b[i++];
                } else if (less(b[i], b[j])) { //第一个数组的当前元素比第二个小,那么先插入第一个数组的(插入后i往后移动一个),第二个不动。
                    a[k] = b[i++];
                } else { //第一个数组比第二个大,那么先插入第二个的,第一个不动
                    a[k] = b[j++];
                }
            }
    
    
    点赞 1 评论 复制链接分享

相关推荐