算法(Algorithms)第4版 练习 2.2.11(3)

发布时间:2017-3-27 7:33:03编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"算法(Algorithms)第4版 练习 2.2.11(3) ",主要涉及到算法(Algorithms)第4版 练习 2.2.11(3) 方面的内容,对于算法(Algorithms)第4版 练习 2.2.11(3) 感兴趣的同学可以参考一下。

关键代码实现:

  public static void sort(Comparable[] input) {        int N = input.length;        aux = input.clone();//must be clone(the same as input)//        StdOut.println("input:" + input + " aux:" + aux);//for test        sort(aux, input, 0, N-1);    }        //take input from source, sort it and put output in destination    //source and destination is the same at the beginning    private static void sort(Comparable[] source, Comparable[] destination, int lo, int hi) {                if(lo >= hi)//just one entry in array            return;                int mid = lo + (hi-lo)/2;        sort(destination, source, lo, mid);//first get input from destination, sort it and put output in source        sort(destination, source, mid+1, hi);        merge(source, destination, lo, mid, hi);//merge sorted source to destination            }        private static void merge(Comparable[] source, Comparable[] destination, int lo, int mid, int hi) {                int i = lo;        int j = mid + 1;        for(int k = lo; k <= hi; k++) {            if(i > mid)                destination[k] = source[j++];            else if(j > hi)                destination[k] = source[i++];            else if(less(source[j], source[i]))                destination[k] = source[j++];            else                 destination[k] = source[i++];        }//        StdOut.println("source:" + source + " destination:" + destination);//        StdOut.printf("merge(source, destination, %4d, %4d, %4d)", lo, mid, hi);//        show(destination);//for test            }

测试用例:

package com.qiusongde;import edu.princeton.cs.algs4.In;import edu.princeton.cs.algs4.StdOut;public class MergeAvoidCopy {        private static Comparable[] aux;        public static void sort(Comparable[] input) {        int N = input.length;        aux = input.clone();//must be clone(the same as input)//        StdOut.println("input:" + input + " aux:" + aux);//for test        sort(aux, input, 0, N-1);    }        //take input from source, sort it and put output in destination    //source and destination is the same in start    private static void sort(Comparable[] source, Comparable[] destination, int lo, int hi) {                if(lo >= hi)//just one entry in array            return;                int mid = lo + (hi-lo)/2;        sort(destination, source, lo, mid);//first get input from destination, sort it and put output in source        sort(destination, source, mid+1, hi);        merge(source, destination, lo, mid, hi);//merge sorted source to destination            }        private static void merge(Comparable[] source, Comparable[] destination, int lo, int mid, int hi) {                int i = lo;        int j = mid + 1;        for(int k = lo; k <= hi; k++) {            if(i > mid)                destination[k] = source[j++];            else if(j > hi)                destination[k] = source[i++];            else if(less(source[j], source[i]))                destination[k] = source[j++];            else                 destination[k] = source[i++];        }//        StdOut.println("source:" + source + " destination:" + destination);//        StdOut.printf("merge(source, destination, %4d, %4d, %4d)", lo, mid, hi);//        show(destination);//for test            }        private static boolean less(Comparable v, Comparable w) {                return v.compareTo(w) < 0;            }        private static void show(Comparable[] a) {                //print the array, on a single line.        for(int i = 0; i < a.length; i++) {            StdOut.print(a[i] + " ");        }        StdOut.println();            }        public static boolean isSorted(Comparable[] a) {                for(int i = 1; i < a.length; i++) {            if(less(a[i], a[i-1]))                return false;        }                return true;            }        public static void main(String[] args) {                //Read strings from standard input, sort them, and print.        String[] input = In.readStrings();//        show(input);//for test        sort(input);        assert isSorted(input);//        show(input);//for test            }}

测试结果:

M E R G E S O R T E X A M P L E input:[Ljava.lang.String;@1b6d3586 aux:[Ljava.lang.String;@4554617csource:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,    0,    0,    1)E M R G E S O R T E X A M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,    2,    2,    3)E M G R E S O R T E X A M P L E source:[Ljava.lang.String;@4554617c destination:[Ljava.lang.String;@1b6d3586merge(source, destination,    0,    1,    3)E G M R E S O R T E X A M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,    4,    4,    5)E M G R E S O R T E X A M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,    6,    6,    7)E M G R E S O R T E X A M P L E source:[Ljava.lang.String;@4554617c destination:[Ljava.lang.String;@1b6d3586merge(source, destination,    4,    5,    7)E G M R E O R S T E X A M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,    0,    3,    7)E E G M O R R S T E X A M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,    8,    8,    9)E E G M O R R S E T X A M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,   10,   10,   11)E E G M O R R S E T A X M P L E source:[Ljava.lang.String;@4554617c destination:[Ljava.lang.String;@1b6d3586merge(source, destination,    8,    9,   11)E G M R E O R S A E T X M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,   12,   12,   13)E E G M O R R S E T A X M P L E source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,   14,   14,   15)E E G M O R R S E T A X M P E L source:[Ljava.lang.String;@4554617c destination:[Ljava.lang.String;@1b6d3586merge(source, destination,   12,   13,   15)E G M R E O R S A E T X E L M P source:[Ljava.lang.String;@1b6d3586 destination:[Ljava.lang.String;@4554617cmerge(source, destination,    8,   11,   15)E E G M O R R S A E E L M P T X source:[Ljava.lang.String;@4554617c destination:[Ljava.lang.String;@1b6d3586merge(source, destination,    0,    7,   15)A E E E E G L M M O P R R S T X A E E E E G L M M O P R R S T X 

性能比较:

For 20000 random Doubles 1000 trialsMerge is 3.4sMergeFasterM is 3.1sMergeUseInsert is 3.2sMergeSkipMerge is 3.3sMergeAvoidCopy is 3.0s


上一篇:hibernate 三种状态的转换
下一篇:标识符(IDentifier)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款