自底向上的归并排序

港控/mmm° 2021-07-24 14:53 420阅读 0赞

# 一 算法分析 #

自底向上的归并排序的归并结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 二 代码 #

package sort;
    
    import common.StdIn;
    import common.StdOut;
    
    /**
     * @className: Merge
     * @description: 自底向上的归并排序
     * @date: 2021/2/27
     * @author: cakin
     */
    public class MergeBU {
    
        public MergeBU() {
        }
    
        /**
         * 功能描述：原地归并
         *
         * @param a   待排序数组
         * @param aux 辅助数组
         * @param lo  下界
         * @param mid 下界和上界的中间位置
         * @param hi  上界限
         * @author cakin
         * @date 2021/2/27
         */
        private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
            // 初始化辅助数组
            for (int k = lo; k <= hi; k++) {
                aux[k] = a[k];
            }
    
            // i:左半边元素，j：右半边元素
            int i = lo, j = mid + 1;
            // 将排好序的元素放回 a 数组
            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++]; // 右半边的当前元素大于等于左半边的当前元素，取左半边元素
            }
        }
    
        /**
         * 功能描述：自底向上的归并排序，将数组a排序
         *
         * @param a 待排序数组
         * @author cakin
         * @date 2021/2/27
         */
        public static void sort(Comparable[] a) {
            int n = a.length;
            Comparable[] aux = new Comparable[n];
            // len:子数组大小，1,2,4,8...
            for (int len = 1; len < n; len *= 2) {
                for (int lo = 0; lo < n - len; lo += len + len) {
                    int mid = lo + len - 1;
                    int hi = Math.min(lo + len + len - 1, n - 1);
                    merge(a, aux, lo, mid, hi);
                }
            }
            assert isSorted(a);
        }
    
        /**
         * 功能描述：v 是否小于 w
         *
         * @param v 待比较元素第一个元素
         * @param w 待比较元素第二个元素
         * @return boolean true：小于 false：大于等于
         * @author cakin
         * @date 2021/2/26
         */
        private static boolean less(Comparable v, Comparable w) {
            return v.compareTo(w) < 0;
        }
    
    
        /**
         * 功能描述：数组的是否已排好序
         *
         * @param a 数组
         * @return boolean true：排好序 false：没排好序
         * @author cakin
         * @date 2021/2/26
         */
        private static boolean isSorted(Comparable[] a) {
            for (int i = 1; i < a.length; i++)
                if (less(a[i], a[i - 1])) return false;
            return true;
        }
    
        /**
         * 功能描述：打印数组
         *
         * @param a 待打印的数组
         * @author cakin
         * @date 2021/2/26
         */
        private static void show(Comparable[] a) {
            for (int i = 0; i < a.length; i++) {
                StdOut.println(a[i]);
            }
        }
    
        /**
         * 功能描述：自底向上的归并排序测试
         *
         * @author cakin
         * @date 2021/2/27
         * @param args 命令行
         */
        public static void main(String[] args) {
            String[] a = StdIn.readAllStrings();
            MergeBU.sort(a);
            show(a);
        }
    }

# 三 测试结果 #

F:\Algorithm\target\classes>java sort.MergeBU < tiny.txt
    A
    E
    E
    L
    M
    O
    P
    R
    S
    T
    X
    
    
    F:\Algorithm\target\classes>java sort.MergeBU < words3.txt
    all
    bad
    bed
    bug
    dad
    dim
    dug
    egg
    fee
    few
    for
    gig
    hut
    ilk
    jam
    jay
    jot
    joy
    men
    nob
    now
    owl
    rap
    sky
    sob
    tag
    tap
    tar
    tip
    wad
    was
    wee
    yes
    yet
    zoo

# 四 各种排序算法性能测试 #

## 1 代码 ##

package sort;
    
    import common.StdOut;
    import common.StdRandom;
    import common.Stopwatch;
    
    /**
     * @ClassName: SortCompare
     * @Description: 各种排序算法性能测试
     * @Date: 2021/2/26
     * @Author: cakin
     */
    public class SortCompare {
        /**
         * 功能描述：算法alg使用的时间
         *
         * @param alg 算法名称
         * @param a   数组
         * @return double 算法使用时间
         * @author cakin
         * @date 2021/2/26
         */
        public static double time(String alg, Comparable[] a) {
            Selection selection = new Selection();
            Insertion insertion = new Insertion();
            Shell shell = new Shell();
            Merge merge = new Merge();
            MergeBU mergebu = new MergeBU();
    
            Stopwatch timer = new Stopwatch();
            if (alg.equals("Selection")) {
                selection.sort(a);
            }
            if (alg.equals("Insertion")) {
                insertion.sort(a);
            }
            if (alg.equals("Shell")) {
                shell.sort(a);
            }
            if (alg.equals("Merge")) {
                merge.sort(a);
            }
            if (alg.equals("MergeBu")) {
                mergebu.sort(a);
            }
    
            return timer.elapsedTime();
        }
    
        /**
         * 功能描述：使用 alg 将T个长度为N的数组排序
         *
         * @param alg 算法
         * @param N   数组长度
         * @param T   进行N次排序
         * @return 排序总时长
         * @author cakin
         * @date 2021/2/26
         */
        public static double timeRandomInput(String alg, int N, int T) {
            double total = 0.0;
            Double[] a = new Double[N];
            for (int t = 0; t < T; t++) {
                // 进行一次测试(生成一个数组并排序)
                for (int i = 0; i < N; i++) {
                    a[i] = StdRandom.uniform();
                }
                total += time(alg, a);
            }
            return total;
        }
    
        /**
         * 功能描述：比较各种排序算法的性能
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/2/26
         */
        public static void main(String[] args) {
            String alg1 = "Selection"; // 选择排序
            String alg2 = "Insertion"; // 插入排序
            String alg3 = "Shell"; // 希尔排序
            String alg4 = "Merge"; // 自顶向下归并排序
            String alg5 = "MergeBu"; // 自底向上归并排序
            int N = 1000;
            int T = 1000;
            double t1 = timeRandomInput(alg1, N, T); // Selection的总时间
            double t2 = timeRandomInput(alg2, N, T); // Insertion的总时间
            double t3 = timeRandomInput(alg3, N, T); // Shell的总时间
            double t4 = timeRandomInput(alg4, N, T); // Merge的总时间
            double t5 = timeRandomInput(alg5, N, T); // MergeBU的总时间
    
            StdOut.printf("For %d random Doubles  %s is %.4f \n", N, alg1, t1);
            StdOut.printf("For %d random Doubles  %s is %.4f\n", N, alg2, t2);
            StdOut.printf("For %d random Doubles  %s is %.4f\n", N, alg3, t3);
            StdOut.printf("For %d random Doubles  %s is %.4f \n", N, alg4, t4);
            StdOut.printf("For %d random Doubles  %s is %.4f \n", N, alg5, t5);
        }
    }

## 2 测试 ##

For 1000 random Doubles  Selection is 1.3010
    For 1000 random Doubles  Insertion is 1.1360
    For 1000 random Doubles  Shell is 0.2040
    For 1000 random Doubles  Merge is 0.2400
    For 1000 random Doubles  MergeBu is 0.2470

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/3622d3d309fc4cc3888d054dec8201d7.png