Java排序算法总结

Java 数组排序算法有很多，之前没有系统性的练习过，很多也不懂，算法这块一直是弱项，因为看不懂，导致不想看，恶性循环，现在是时候系统的看一下了（希望能坚持下去🙃），学习于 CyC2018。

准备

既然是“排序”，肯定就会涉及到元素大小的比较和位置的互换，最好将其抽取为共用的方法，可以用 Java 的抽象类和继承了（听起来很👎，使用之后...真香）。

将元素大小比较和位置互换的方法放到抽象父类中，子类可以通过继承的方式复用，代码如下：

public abstract class Sort<T extends Comparable<T>> {

    /**
     * 排序方法
     *
     * @param nums 待排数组
     */
    public abstract void sort(T[] nums);

    /**
     * 判断首参数是否小于第二个参数
     *
     * @param t1 首元素
     * @param t2 第二参数
     * @return 首参数是否小于第二个参数
     */
    protected boolean less(T t1, T t2) {
        return t1.compareTo(t2) < 0;
    }

    /**
     * 交换给定数组指定位置的两元素
     *
     * @param nums 数组
     * @param i    索引
     * @param j    索引
     */
    protected void swap(T[] nums, int i, int j) {
        T t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

}

至于这个 Comparable 接口，看名字都知道是一个和“比较”有关的接口了，该接口只有一个 compareTo() 方法，看泛型 T 的具体类型了。

选择排序

原理： 选出数组中最小的元素与第一个互换，再从剩下的选出最小的与第二个互换，不断循环至最后，直到数组排完序。

public class SelectionSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int executeTimes = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            // 默认当前元素是最小的，依次向后排
            int minIdx = i;
            for (int j = i + 1; j < nums.length; j++) {
                executeTimes += 1;
                // 比较第 i 个元素之后的所有元素，如有更小的，赋值给 minIdx
                if (less(nums[j], nums[minIdx])) {
                    minIdx = j;
                }
            }
            // 第 i 个元素与一轮循环最小的互换
            swap(nums, i, minIdx);
        }
        System.err.println("选择 executeTimes ==>>" + executeTimes);
        System.out.println("选择排序后 ==>>" + Arrays.toString(nums));
    }
}

弊端： 即时是一个大部分已排好序的数组，也要进行同样多次数的比较。

时间复杂度： 可以看到如果数组元素个数为 n，两轮循环，每轮循环次数都是 n，时间复杂度为 O(n×n×1)，即 O(n²)。

冒泡排序

原理： 从左至右不断交换相邻逆序元素，直到将最大的一直向右冒出来。

public class BubbleSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int executeTimes = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                executeTimes += 1;
                // 后面的比前面的大
                if (less(nums[j + 1], nums[j])) {
                    swap(nums, j, j + 1);
                }
            }
        }
        System.err.println("冒泡 executeTimes ==>>" + executeTimes);
        System.out.println("冒泡排序后 ==>>" + Arrays.toString(nums));
    }
}

上面的代码有一个问题，即时数组已经有序，但是代码还是会执行判断是否互换到数组最后，可以加个标识符，在逆序的两元素互换的时候确定是尚未完全有序，循环入口加上该标识符的判断，更改后的代码如下：

public class BubbleSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int executeTimes = 0;
        boolean hasSorted = false;
        for (int i = nums.length - 1; i > 0 && !hasSorted; i--) {
            hasSorted = true;
            for (int j = 0; j < i; j++) {
                executeTimes += 1;
                // 后面的比前面的大
                if (less(nums[j + 1], nums[j])) {
                    // 需要互换，尚未完全有序
                    hasSorted = false;
                    swap(nums, j, j + 1);
                }
            }
        }
        System.err.println("冒泡 executeTimes ==>>" + executeTimes);
        System.out.println("冒泡排序后 ==>>" + Arrays.toString(nums));
    }
}

时间复杂度： O(nxn)=O(n²)

插入排序

原理： 从左向右，每次将元素插入到左侧已排序的数组中，使左侧在插入之后依然有序。

public class InsertionSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) {
                // 相当于比较的是第 i-1 个和第 i 个元素，一直向前
                swap(nums, j, j - 1);
                System.out.println(Arrays.toString(nums));
            }
        }
        System.out.println("插入排序后 ===>>>" + Arrays.toString(nums));
    }
}

时间复杂度： 可以看到内循环中的条件如果不满足，即数组已有序，此时为 O(n)；最坏情况是内循环、外循环都是 n 次，此时为 O(nxn)=O(n²)。

未完，待续！

本文作者：Star Wang

本文链接：https://tryme.wang/archives/201901/java-sort-algorithm.html

转载时请注明出处