选择排序和排序算法性能比较

矫情吗；* 2021-07-25 00:46 423阅读 0赞

# 一 可视化比较 #

![20210226200041647.png][]

# 二 实战 #

## 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使用的时间
         *
         * @author cakin
         * @date 2021/2/26
         * @param alg 算法名称
         * @param a 数组
         * @return double 算法使用时间
         */
        public static double time(String alg, Comparable[] a) {
            Selection selection = new Selection();
            Insertion insertion = new Insertion();
    
            Stopwatch timer = new Stopwatch();
            if (alg.equals("Selection")) {
                selection.sort(a);
            }
            if (alg.equals("Insertion")) {
                insertion.sort(a);
            }
            return timer.elapsedTime();
        }
    
        /**
         * 功能描述：使用 alg 将T个长度为N的数组排序
         *
         * @author cakin
         * @date 2021/2/26
         * @param alg 算法
         * @param N 数组长度
         * @param T 进行N次排序
         * @return 排序总时长
         */
        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;
        }
    
        /**
         * 功能描述：比较选择排序和插入排序性能
         *
         * @author cakin
         * @date 2021/2/26
         * @param args 命令行
         */
        public static void main(String[] args) {
            String alg1 = args[0];
            String alg2 = args[1];
            int N = Integer.parseInt(args[2]);
            int T = Integer.parseInt(args[3]);
            double t1 = timeRandomInput(alg1, N, T); // alg1的总时间
            double t2 = timeRandomInput(alg2, N, T); // alg2的总时间
            StdOut.printf("For %d random Doubles\n  %s is", N, alg1);
            StdOut.printf(" %.1f times faster than %s\n", t2 / t1, alg2);
        }
    }

## 2 测试 ##

F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 0.8 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.3 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.4 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.0 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.2 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.3 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.3 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.1 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.5 times faster than Selection
    
    
    F:\Algorithm\target\classes>java sort.SortCompare Insertion Selection 1000 100
    For 1000 random Doubles
      Insertion is 1.4 times faster than Selection

## 3 说明 ##

使用该算法可以从实践的基础上比较各排序算法的性能。

[20210226200041647.png]: /images/20210724/6e3307a6c2924110985453172c317871.png