2、排序基础

1、选择排序

选择排序是一个基础的排序算法，它的复杂度是 O(n²)

public class SelectionSort {
    
    private SelectionSort() {
    }
    
    private static <E> void swap(E[] arr, int a, int b) {
        E k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }

    /**
     * 正着排
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 循环不变量: arr[0, i) 已排序
            // 循环体维持循环不变量: 向 arr[i] 放置剩余元素中最小的元素
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) minIndex = j;
            }
            swap(arr, i, minIndex);
        }
    }

    /**
     * 倒着排
     */
    public static <E extends Comparable<E>> void sort1(E[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            // 循环不变量: arr(i, n] 已排序
            // 循环体维持循环不变量: 向 arr[i] 放置剩余元素中最大的元素
            int maxIndex = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j].compareTo(arr[maxIndex]) > 0) maxIndex = j;
            }
            swap(arr, i, maxIndex);
        }
    }
}

2、插入排序

插入排序是一个基础的排序算法，它的复杂度是 O(n²)
但是我们可以对它进行优化，使其对近乎有序的数据排序变得更快，对完全有序的数据排序复杂度为 O(n)
我们的优化是非常重要的，优化后的插入排序虽然最坏情况下复杂度还是 O(n²)，但是高级的排序算法也会用到它

public class InsertionSort {

    private InsertionSort() {
    }

    private static <E extends Comparable<E>> void swap(E[] arr, int a, int b) {
        E k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }

    /**
     * 正着排
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 循环不变量: arr[0, i) 已局部排序
            // 循环体维持循环不变量: 将 arr[i] 插入合适的位置(也可以理解为调整 arr[0...i] 中与 i 绑定的逆序数对)
            E k = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && arr[j - 1].compareTo(k) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = k;
        }
    }

    /**
     * 插入排序 arr[l, r]
     */
    public static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            E k = arr[i];
            int j;
            for (j = i; j - 1 >= l && arr[j - 1].compareTo(k) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = k;
        }
    }

    /**
     * 倒着排
     */
    public static <E extends Comparable<E>> void sort3(E[] arr) {
        for (int i = arr.length - 2; i >= 0; i--) {
            // 循环不变量: arr(i, n] 已局部排序
            // 循环体维持循环不变量: 将 arr[i] 插入合适的位置(也可以理解为调整 arr[i...n] 中与 i 绑定的逆序数对)
            E k = arr[i];
            int j;
            for (j = i; j + 1 < arr.length && k.compareTo(arr[j + 1]) > 0; j++) {
                arr[j] = arr[j + 1];
            }
            arr[j] = k;
        }
    }

    /**
     * 倒着排, 基于交换
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = arr.length - 2; i >= 0; i--) {
            // 循环不变量: arr(i, n] 已局部排序
            // 循环体维持循环不变量: 将 arr[i] 插入合适的位置(也可以理解为调整 arr[i...n] 中与 i 绑定的逆序数对)
            for (int j = i; j + 1 < arr.length && arr[j].compareTo(arr[j + 1]) > 0; j++) {
                swap(arr, j, j + 1);
            }
        }
    }

    /**
     * 正着排, 基于交换
     */
    public static <E extends Comparable<E>> void sort1(E[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 循环不变量: arr[0, i) 已局部排序
            // 循环体维持循环不变量: 将 arr[i] 插入合适的位置(也可以理解为调整 arr[0...i] 中与 i 绑定的逆序数对)
            for (int j = i; j - 1 >= 0 && arr[j - 1].compareTo(arr[j]) > 0; j--) {
                swap(arr, j, j - 1);
            }
        }
    }
}