Star

Java排序算法总结
Java 数组排序算法有很多,之前没有系统性的练习过,很多也不懂,算法这块一直是弱项,因为看不懂,导致不想看,恶性...
扫描右侧二维码阅读全文
28
2019/01

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(n2)。


冒泡排序

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

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(n2)


插入排序

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

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(n2)。


未完,待续!
Last modification:January 30th, 2019 at 04:40 pm
If you think my article is useful to you, please feel free to appreciate

One comment

  1. Star

    东西有点多啊

Leave a Comment