三种排序方法的实现以及性能比较

最近开始学算法了,在学校搞定了三种排序,刚刚在家里实践,现在就依次讲讲吧

首先,我所说的排序就是将数组中的数据按照一定规律(升序或降序)排列
其次,我是用Java实现的,因此用到了泛型(为了算法能更广泛的运用)

那么就先依次上代码吧,在此之前我先利用Java的继承体系做了一个排序模板(里面记录了所有排序都必定会要用到的方法)

Sort.java =>所有排序算法的父类

package life.abalone.sort;

/**
 * Create by Abalone
 * CreateTime: 2020/11/7 12:40
 * 排序类模板
 */

abstract class Sort<T> {
    /**
     * 判断v是否小于w
     * @param v 传递值a
     * @param w 传递值b
     * @return 当v小于w时返回true
     */
    protected boolean less(Comparable<T> v, Comparable<T> w) {
        return v.compareTo((T) w) < 0;
    }

    /**
     * 判断v是否大于w
     * @param v 传递值a
     * @param w 传递值b
     * @return 当v大于w时返回true
     */
    protected boolean more(Comparable<T> v, Comparable<T> w) {
        return v.compareTo((T) w) > 0;
    }

    /**
     * 交换数组中元素的位置
     * @param a 数组引用
     * @param i 下标为i的元素
     * @param j 下标为j元素
     */
    protected void exch(Comparable<T>[] a, int i, int j) {
        Comparable<T> t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     * @param a 数组引用
     */
    protected void show(Comparable<T>[] a) {
        for (Comparable<T> comparable : a) {
            System.out.print(comparable+" ");
        }
        System.out.println();
    }

    /**
     * 判断数组是否为升序
     * @param a 数组引用
     * @return true表示升序
     */
    protected boolean isSortedASC(Comparable<T>[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }

    /**
     * 判断数组是否为降序
     * @param a 数组引用
     * @return true表示降序
     */
    protected boolean isSortedDESC(Comparable<T>[] a) {
        for (int i = 1; i < a.length; i++) {
            if (more(a[i], a[i - 1]))
                return false;
        }
        return true;
    }
}

这个类里面使用了abstract关键字,即将类虚拟化,用于继承,不允许被直接实例化,以及泛型,用于广泛使用.

那么对于排序算法的具体实现,我一共写了三种,分别是:

SelectSort => 选择排序
InsertSort => 插入排序
QuickSort => 快速排序
其中,每一个排序都分为了DESC(降序)和ASC(升序) 两种实现

以下分别是他们的代码实现:

(选择排序)SelectSort.java:

package life.abalone.sort;

/**
 * Create by Abalone
 * CreateTime: 2020/11/7 9:45
 * 选择排序,数据移动最少
 */

public class SelectSort<T> extends Sort<T> {
    public void sortASC(Comparable<T>[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (less(a[i], a[j])) exch(a, i, j);
            }
        }
    }

    public void sortDESC(Comparable<T>[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (more(a[i], a[j])) exch(a, i, j);
            }
        }
    }
}

(插入排序)InsertSort.java:

package life.abalone.sort;

/**
 * Create by Abalone
 * CreateTime: 2020/11/7 12:41
 * 插入排序(升级版)
 */

public class InsertSort<T> extends Sort<T> {
    public void sortDESC(Comparable<T>[] a) {
        int n = a.length;
        int exchanges = 0;
        for (int i = n-1; i > 0; i--) {
            if (more(a[i], a[i-1])) {
                exch(a, i, i-1);
                exchanges++;
            }
        }
        if (exchanges == 0) return;
        for (int i = 2; i < n; i++) {
            Comparable<T> v = a[i];
            int j = i;
            while (more(v, a[j-1])) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = v;
        }
    }

    public void sortASC(Comparable<T>[] a) {
        int n = a.length;
        int exchanges = 0;
        for (int i = n-1; i > 0; i--) {
            if (less(a[i], a[i-1])) {
                exch(a, i, i-1);
                exchanges++;
            }
        }
        if (exchanges == 0) return;
        for (int i = 2; i < n; i++) {
            Comparable<T> v = a[i];
            int j = i;
            while (less(v, a[j-1])) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = v;
        }
    }
}

(快速排序)QuickSort:
PS:代码量多的原因仅仅是因为我自己没有去重构,这里的代码实际上是降序和升序两个的,重构之后的代码量会少很多(但是就没有这么直观了)

package life.abalone.sort;

import edu.princeton.cs.algs4.StdRandom;

/**
 * Create by Abalone
 * CreateTime: 2020/11/7 14:54
 */

public class QuickSort<T> extends Sort<T> {
    public void sortASC(Comparable<T>[] a) {
        StdRandom.shuffle(a);
        sortASC(a, 0, a.length - 1);
    }

    private void sortASC(Comparable<T>[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partitionASC(a, lo, hi);
        sortASC(a, lo, j - 1);
        sortASC(a, j + 1, hi);
    }

    private int partitionASC(Comparable<T>[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable<T> v = a[lo];
        while (true) {
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (i == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    public void sortDESC(Comparable<T>[] a) {
        StdRandom.shuffle(a);
        sortDESC(a, 0, a.length - 1);
    }

    private void sortDESC(Comparable<T>[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partitionDESC(a, lo, hi);
        sortDESC(a, lo, j - 1);
        sortDESC(a, j + 1, hi);
    }

    private int partitionDESC(Comparable<T>[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable<T> v = a[lo];
        while (true) {
            while (more(a[++i], v)) if (i == hi) break;
            while (more(v, a[--j])) if (i == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
}

基本的了解完了这三个算法的代码,我们来对这三个排序的速度进行一个测试(这三个算法以后有机会的话会自己再讲的)

首先确立测试目的: 计算三个算法分别在Integer类型数组的元素量为:100,250,750,1500,15000的运行时间.
PS:Integer为Java对int类型的包装类,因为用了泛型所以就不方便用int了
然后给出测试时间的方案(这里直接用时间差):

package life.abalone.tools;

/**
 * Create by Abalone
 * CreateTime: 2020/11/7 14:14
 */

public class TimeCount {
    long startTime;
    public void start() {
        startTime = System.currentTimeMillis();
    }

    public void count() {
        //返回距离开始时间的差
        System.out.println(System.currentTimeMillis() - startTime);
    }
}

接下来是确定数据源:
当数据量为:100,250,750,1500时,使用的数据源在这里:
测试数据下载
关于上方测试数据的获取,是通过以下代码获得的:

new Random().ints(10, 0, 750).toArray();

屏幕截图 2020-11-07 163816
当数据量为15000时,由于不方便直接放在数组中,因此直接随机,不是固定数字,但是数据仍然是由上方图片获得的,因此可以大致保证测试准确

紧跟着的是我的设备配置
- CPU: Intel Core i5-8250U
- RAM: 16G
- 其他的就没必要展示了(丢脸)
然后是测试方式:
每一种算法分别在每一个数据量的情况下运行三次,然后取三次运行时间的平均值

测试代码(Test.java):

package life.abalone.sort;

import life.abalone.tools.TimeCount;

import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * Create by Abalone
 * CreateTime: 2020/11/7 9:59
 * 算法运行测试
 */

public class Test {
    public static void main(String[] args) {
        QuickSort<Integer> sqs = new QuickSort<>();
        InsertSort<Integer> sis = new InsertSort<>();
        SelectSort<Integer> sss = new SelectSort<>();

        TimeCount t = new TimeCount();
        int[] num = new Random().ints(10, 0, 15000).toArray();
        //下面两行数据用于在数据量为15000时将int类型数组转为Integer
        IntStream stream = Arrays.stream(num);
        Integer[] num1 = stream.boxed().toArray(Integer[]::new);

        t.start();
        sis.sortASC(num1);
        t.count();

        t.start();
        sss.sortASC(num1);
        t.count();

        t.start();
        sqs.sortASC(num1);
        t.count();
    }
}

测试结果
整理为表格后如图:

总结:

SelectSort(选择排序),InsertSort(插入排序),QuickSort(快速排序)在测试数据为Integer类型时的一般情况下大致符合以下情况:

当数据量 小于250 时,InsertSort速度最快,QuickSort速度最慢,但三个算法之间差别不大
当数据量间于250与750时: InsertSort速度最快,SelectSort速度最慢,且SelectSort速度与其他两个算法开始产生一定差距
当数据量大于750时,QuickSort最快,其他两个算法相对慢的趋势更大(也就是说,数据越多,慢得程度相对更大,而快速排序速度减慢的幅度较小)
当数据量大于15000时,三个算法之间的差距非常明显,其中快速排序,插入排序,选择排序三个算法的运行时间比大致为: 11:233:600

以上是客观总结,最后是主观总结:

快速排序=>永远の神
插入排序=>暂时の神
选择排序=>自己看着办

Q.E.D.