一、选择排序 Selection Sort

算法思想：比较简单，请看代码理解

复杂度分析：O(N^2)

public static <E> void selectionSort(E[] arr, int n, Compare<E> compare) {

    for (int i = 0; i < n - 1; i++) {
        int temp = i;
        for (int j = i + 1; j < n; j++) {
            if(compare.compare(arr[j], arr[temp]) < 0)
                temp = j;
        }

        E exchange = arr[i];
        arr[i] = arr[temp];
        arr[temp] = exchange;
    }
}

二、冒泡排序（+优化）

优化思路：记录最后一次交换元素的位置，当下一此遍历到这里时，后面的内容就可以不用再去遍历比较了；
数组顺序越趋近排序顺序，性能越好（整体比插入排序弱。）

复杂度分析：
- 未优化前：O(N^2)
- 优化之后：最坏O(N^2)；最好O(N)

import java.util.Comparator;
public class BubbleSort {
    
    public static <E> void bubbleSort(E[] arr, Comparator<E> comparator) {
        // 记录最后一次交换的位置，初始值为末尾元素
        int lastChange = arr.length - 1;
        int recordChange = lastChange;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < lastChange; j++) {
                if(comparator.compare(arr[j + 1], arr[j]) < 0) {
                    swap(arr, j, j + 1);
                    recordChange = j;
                }
            }
            // 提示下一次遍历遍历到此就OK了
            lastChange = recordChange;
        }
    }

    public static <E> void swap(E[] arr, int first, int last) {
        E exchange = arr[first];
        arr[first] = arr[last];
        arr[last] = exchange;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,3,7,0,7,5,3,2,8,5,7,0,9,0,3,5,7,8,2,3,};
        bubbleSort(arr, (a, b) -> b - a);
        for (Integer integer : arr) {
            System.out.print(integer + ", ");
        }
    }
}

三、插入排序 Insertion Sort（+优化）

思想：以升序为例，从第二个位置开始，将当前索引值保留一份，递归式的与前一个进行比较，如果前一个值比当前值大，则将前一个
值复制到当前位置....直到前一个值小于当前的值，此时将保留的值保存到此位置！

复杂度分析：

• 最坏的情况：O(N^2)
• 最好的情况：近乎O(N)

适用场景：数组顺序越趋近排序顺序，性能越好

import java.util.Comparator;
public class InsertionSort {

    public static <E> void insertionSort(E[] arr, Comparator<E> comparator) {
        for (int i = 0; i < arr.length; i++) {
            E exchange = arr[i];
            int j = i;
            for (; j > 0 && comparator.compare(exchange, arr[j - 1]) < 0 ; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = exchange;
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {9, 0, 9, 0, 3, 6, 9, 1, 4, 3, 9, 6, 3, 7, 2, 0, 1, 2, 8};
        insertionSort(arr, (a, b) -> a - b);
        for (Integer integer : arr) {
            System.out.print(integer + ", ");
        }
    }
}

折半查找法,中间位置的索引采用向上取整的方式。

import java.util.Comparator;

public class HalfSort {

    public static <E> void halflSort(E[] arr, Comparator<E> comparator) {

        // 折半查找法
        for (int i = 0; i < arr.length; i++) {
            E exchange = arr[i];
            int from = findPlace(arr, exchange, 0, i, comparator);
            move(arr, exchange, from, i);
        }
    }

    // 利用二分法找到该插入的位置
    public static <E> int findPlace(E[] arr, E exchange, int left, int right, Comparator<E> comparator) {
        while (true) {

            // 终止条件
            if(left + 1 == right) {
                if(left == 0  && comparator.compare(exchange, arr[0]) < 0)
                    return left;

                return right;
            }

            // middle就是当前位置,向上取整
            int middle = (int)Math.ceil((left + right ) / 2.0);

            if(comparator.compare(exchange, arr[middle]) < 0) {
                right = middle;
            } else if(comparator.compare(exchange, arr[middle]) > 0) {
                left = middle;
            } else
                return middle;
        }

    }

    // 根据当前遍历的位置以及需要插入的位置进行交换。
    public static <E> void move(E[] arr, E exchange, int from, int to){
        for (int i = to; i > from ; i--) {
            arr[i] = arr[i - 1];
        }

        arr[from] = exchange;
    }


    public static void main(String[] args) {

        Integer[] arr = {0,1,0,7,8,3,1,6,8,3,1,2,0,3,4,6,8,2,1,4,8,9,3,0};
        halflSort(arr, (a, b) -> a - b);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ", ");
        }
    }

}

四、希尔排序

希尔排序是对插入排序的深层次优化,
缩小增量排序,(大致过程自行百度)

整体思想就是让数组逐渐趋近于有序化，

public final class ShellSort {

    public static void sort(Comparable[] arr){

        int n = arr.length;

        // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
        int h = 1;
        while (h < n/3) h = 3*h + 1;

        while (h >= 1) {

            // h-sort the array
            for (int i = h; i < n; i++) {

                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
                Comparable e = arr[i];
                int j = i;
                for ( ; j >= h && e.compareTo(arr[j-h]) < 0 ; j -= h)
                    arr[j] = arr[j-h];
                arr[j] = e;
            }

            h /= 3;
        }
    }
}