直接插入排序、简单选择排序、冒泡排序、快速排序

1、直接插入排序

空间复杂度：O(1)

时间复杂度：最优O(n)，最坏O(n^2) ，平均O(n^2) 。

/**
 * 直接插入排序：下一个数在插入前面的有序数列时排序
 */
public class Insertion {

    public static void main(String[] args) {
        int[] arr = {10, 9, 4, 8, 6, 7, 5, 3, 2, 1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
 			//当前插入的数
            int temp = arr[i];
            
            //有序列中最后一个元素的下标
            int cur = i - 1;

            while (cur >= 0 && temp < arr[cur]) {

                arr[cur + 1] = arr[cur];

                cur--;
            }
            arr[cur + 1] = temp;
        }
    }
}

2、简单选择排序

空间复杂度：O(1)

时间复杂度：最优O(n^2)，最坏O(n^2)，平均O(n^2)

/**
 * 简单选择排序：遍历数组选择最小的数放在本次循环第一个
 */
public class SelectSort {

    public static void main(String[] args) {

        int[] arr = {10, 9, 4, 8, 6, 7, 5, 3, 2, 1, -1};

        selectSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void selectSort(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {

            //当前最小数的下标，默认本次循环第一个数
            int minIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

3、冒泡排序

空间复杂度：O(1)

时间复杂度：最优O(n)，最坏O(n^2)，平均O(n^2)

/**
 * 冒泡排序：前面的数大于后面的数则交换
 */
public class Bubble {

    public static void main(String[] args) {

        int[] arr = new int[]{10, 9, 4, 8, 6, 7, 5, 3, 2, 1};

        for (int i = 0; i < arr.length - 1; i++) {

            //没有改变过则表示顺序已经排好，提前结束
            boolean flag = false;

            for (int j = 0; j < arr.length - 1 - i; j++) {
                int temp = 0;

                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println();
            if (!flag) {
                break;
            }
            flag = false;
        }
        System.out.println(Arrays.toString(arr));
    }
}

4、快速排序

空间复杂度：O(logn)~O(n)

时间复杂度：最优O(nlogn)，最坏O(n^2)，平均O(nlogn)

/**
 * 快速排序：随便找一个基数
 *         该数组左右两边各一个哨兵
 *         后面的哨兵先向前走，找到小于基数的数则停止
 *         前面的哨兵再向后走，找到大于基数的数则停止
 *         进行交换
 *         俩哨兵相遇时，把基数与相遇时的数字交换
 *         基数两边的数组分别进行递归
 *         直到左哨兵要大于右哨兵时停止
 */
public class Quick {
    public static void main(String[] args) {
        int[] arr = {10, 9, 4, 8, 6, 7, 5, 3, 2, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {

        if (left > right) {
            return;
        }

        int l = left;
        int r = right;
        int sentinel = arr[left];

        while (l < r) {

            //从后往前走找到小于基数的那个数
            while (sentinel <= arr[r] && l < r) {
                r--;
            }

            //从前往后走找到大于基数的那个数
            while (sentinel >= arr[l] && l < r) {
                l++;
            }

            if (l < r) {
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        //哨兵相遇的数和基数换位
        arr[left] = arr[l];
        arr[l] = sentinel;

        //左边部分递归
        quickSort(arr, left, r - 1);

        //右边部分递归
        quickSort(arr, l + 1, right);
    }
}

5、希尔排序

空间复杂度：O(1)

时间复杂度：最优O(n0)，最坏O(n^1.3-1.4)，平均O(n^2)

**
 * 希尔排序:  先按照步长分组（通常一开始是长度/2），然后在每组之间进行插入排序
 *          每次循环步长都/2，最后步长为1时排序完成
 *
 * 原理详细视频：https://www.bilibili.com/video/BV1rE411g7rW?from=search&seid=1367894135618905857
 */
public class Shell {

    public static void main(String[] args) {

        int[] arr = {10, 9, 4, 8, 6, 7, 5, 3, 2, 1, -1};

        shellSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {

        //定出步长，每次循环减半
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {

            //从第二组的第一个数开始
            for (int i = gap; i < arr.length; i++) {

                //如果后面的数小于前面的数则执行直接插入排序
                if (arr[i] < arr[i - gap]) {

                    int j = i;
                    int temp = arr[j];

                    while (j - gap >= 0 && temp < arr[j - gap]) {

                        arr[j] = arr[j - gap];

                        j -= gap;
                    }

                    arr[j] = temp;
                }
            }
        }
    }
}