简单选择排序

每次循环找到未排序的最小的元素，与未排序的第一个元素交换，重复此过程直到整体有序。
所有情况下的时间复杂度均为O(n^2)，空间复杂度为O(1)

public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[minIndex] > nums[j]) {
                minIndex = j;
            }
        }
        int temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
}

直接插入排序

每次处理未排序的第一个元素，将其向左移动到已排序元素的适当位置，重复此过程直到整体有序。
序列基本有序的情况下适合用直接插入排序。
最好情况是序列已经有序，时间复杂度为O(n)
平均和最坏情况的时间复杂为是O(n^2)
空间复杂度为O(1)

public static void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
    }
}

希尔排序

每次循环选取一个步长(例如数组长度的一半)，将距离等于步长的元素作为一组，各组组内进行直接插入排序。下次循环步长-1，重复此过程直到步长为1，即可完成排序。
最好情况与直接插入排序相同，即序列已经有序，时间复杂度为O(n)
平均情况下时间复杂度约为O(n^{1.3})
最坏情况为逆序，时间复杂度为O(n^2)
空间复杂度为O(1)

public static void shellSort(int[] nums) {
    // 以nums.length/2作为初始步长
    for (int step = nums.length / 2; step > 0; step--) {
        for (int offset = 0; offset < step; offset++) {
            for (int i = offset + step; i < nums.length; i += step) {
                for (int j = i; j > offset; j -= step) {
                    if (nums[j] < nums[j - step]) {
                        int temp = nums[j];
                        nums[j] = nums[j - step];
                        nums[j - step] = temp;
                    }
                }
            }
        }
    }
}

冒泡排序

从右往左比较相邻的两个元素，如果右边的元素小于左边，则交换位置，每次循环会把未排序的最小元素换到最左边，重复此过程直到整体有序。
有一种优化方式，是用flag记录此轮循环中是否发生过交换，如果一次都没交换，则说明排序已经完成，可以直接结束。考研408默认采用这种方式。
优化后的冒泡排序最好情况为序列已经有序，时间复杂度为O(n)
平均和最坏情况时间复杂度为O(n^2)
空间复杂度为O(1)

public static void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = nums.length - 1; j > i; j--) {
            if (nums[j] < nums[j - 1]) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
    }
}

public static void bubbleSort2(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        boolean swapped = false;
        for (int j = nums.length - 1; j > i; j--) {
            if (nums[j] < nums[j - 1]) {
                swapped = true;
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
        if (!swapped) {
            return;
        }
    }
}

快速排序

每次选取一个元素作为枢轴pivot(例如最左边的元素)，将比枢轴小的元素换到左边，比枢轴大的元素换到右边，得到左右两个子序列，对两个子序列分别递归调用此方法，直到每个序列只有一个元素。
快速排序的辅助空间用于记录递归树，因此空间复杂度等于递归深度。
最好和平均情况时间复杂度为O(n\log_2n)，递归深度为\log_2n，空间复杂度为O(\log_2n)
最坏情况为序列已经按顺序或逆序排列，时间复杂度为O(n^2)，因为此时的枢轴不能将序列分为两个子序列，递归深度为n，空间复杂度为空间复杂度为O(n)
有一种优化的方式是取随机位置的元素作为枢轴，而不是第一个元素，这样可以避免最坏情况时间和空间复杂度过大的问题。考研408默认不采用这种方式。

public static void quickSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left;
    int j = right;
    int pivot = nums[left];
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        if (i < j) nums[i++] = nums[j];
        while (i < j && nums[i] < pivot) i++;
        if (i < j) nums[j--] = nums[i];
    }
    nums[i] = pivot;
    quickSort(nums, left, i - 1);
    quickSort(nums, j + 1, right);
}

二路归并排序

归并排序的思想是“分而治之”。
“分”的过程是如果元素数量大于1，则将序列分为尽可能等长的两个子序列。
“治”的过程是将子序列两两合并，合并后的序列内部是有序的，重复合并过程直到全部完成。
所有情况的时间复杂度均为O(n\log_2n)，空间复杂度为O(n)，辅助空间用于记录子序列。
归并排序可用于外部排序，数据占用的存储空间大于内存也能使用，因为子序列合并的过程不需要把全部数据读取到内存中。
归并排序是稳定的。

public static int[] mergeSort(int[] nums) {
    if (nums.length == 1) {
        return nums;
    }

    // 分
    int middle = nums.length / 2;
    int[] left = new int[middle];
    int[] right = new int[nums.length - middle];
    for (int i = 0; i < nums.length; i++) {
        if (i < middle) {
            left[i] = nums[i];
        } else {
            right[i - middle] = nums[i];
        }
    }

    // 治
    return merge(mergeSort(left), mergeSort(right));

}

public static int[] merge(int[] left, int[] right) {
    // i, j分别为left, right的索引
    int i = 0, j = 0;
    int[] result = new int[left.length + right.length];
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result[i + j] = left[i++];
        } else {
            result[i + j] = right[j++];
        }
    }
    while (i < left.length) {
        result[i + j] = left[i++];
    }
    while (j < right.length) {
        result[i + j] = right[j++];
    }
    return result;
}

基数排序

基数排序主要用于整数。
对于十进制正整数，先按个位数字排序，再按十位数排序，以此类推，直到完成最大数字最高位的排序。
每一位的排序不是基于比较的，而是直接根据值分配到对应的桶。
基数排序是稳定的，因为桶中的数可以按放入的顺序取出。
时间复杂度为O(d\cdot (n+r))，其中n是排序元素个数，d是数字的最大位数，r是进制，加号表示取最大值。
从下面的代码可以看出外层循环次数是d，内层循环次数是2n+r，通常n远大于r，所以时间复杂度也能简写为O(d\cdot n)
空间复杂度为O(rn)，也能简写为O(n)

public static int getMaxDigit(int[] nums) {
    int maxValue = Integer.MIN_VALUE;
    for (int num : nums) {
        maxValue = Math.max(maxValue, num);
    }
    int maxDigit = 0;
    while (maxValue > 0) {
        maxValue /= 10;
        maxDigit++;
    }
    return maxDigit;
}


public static void radixSort(int[] nums) {
    int maxDigit = getMaxDigit(nums);
    // d表示倒数第几位
    for (int d = 0; d < maxDigit; d++) {
        // 初始化10个桶
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }

        // 获取当前位的值，放在对应的桶中
        for (int num : nums) {
            int n = num / (int) Math.pow(10, d) % 10;
            buckets.get(n).add(num);
        }

        // 依次从桶中取出来
        // 虽然有两层循环，但复杂度为O(n)，因为取出n个数
        int j = 0;
        for (int i = 0; i < 10; i++) {
            for (int num : buckets.get(i)) {
                nums[j++] = num;
            }
        }
    }
}

堆排序

构造大根堆，然后将堆顶元素与未排序的最后一个元素交换，堆的长度减1，然后重新调整为大根堆，重复此过程直到堆为空。
时间复杂度为O(n\log n)，建堆时间复杂度为O(n)
空间复杂度为O(1)，因为堆是完全二叉树，可以用数组来表示
不稳定。

public static void heapify(int[] nums, int i, int length) {
    int left = i * 2;
    int right = i * 2 + 1;
    int maxIndex = i;
    if (left < length && nums[left] > nums[maxIndex]) {
        maxIndex = left;
    }
    if (right < length && nums[right] > nums[maxIndex]) {
        maxIndex = right;
    }
    if (i != maxIndex) {
        int temp = nums[i];
        nums[i] = nums[maxIndex];
        nums[maxIndex] = temp;
        heapify(nums, maxIndex, length);
    }
}

private static void buildMaxHeap(int[] nums, int length) {
    for (int i = length / 2; i >= 0; i--) {
        heapify(nums, i, length);
    }
}

private static void heapSort(int[] nums) {
    buildMaxHeap(nums, nums.length);
    int length = nums.length;
    while (length > 0) {
        int temp = nums[0];
        nums[0] = nums[length - 1];
        nums[length - 1] = temp;
        length--;
        heapify(nums, 0, length);
    }
}

总结

以上八种排序算法中，
稳定的有：冒泡排序、归并排序、基数排序
不稳定的有：简单选择排序、直接插入排序、希尔排序、快速排序、二路归并排序

平均情况下时间复杂度为O(n\log n)的有：快速排序、二路归并排序、堆排序
平均情况下时间复杂度为O(n^2)的有：简单选择排序、冒泡排序、插入排序

平均情况下空间复杂度为O(1)的有：堆排序、直接插入排序、希尔排序、简单选择排序、冒泡排序
平均情况下空间复杂度为O(n)的有：归并排序
平均情况下空间复杂度为O(n\log n)的有：快速排序

与初始状态有关的有：冒泡排序、快速排序、直接插入排序、希尔排序
与初始状态无关的有：简单选择排序、二路归并排序、堆排序、基数排序

基数排序是基于分配的排序，其他七种都是基于比较的排序

归并排序既能用于内部排序，也能用于外部排序，其他七种都只能用于内部排序

直接插入排序、希尔排序都属于插入排序
简单选择排序、堆排序都属于选择排序
冒泡排序、快速排序都属于交换排序

基本有序时最适合用直接插入排序，虽然复杂度相同，但比较次数更少
有序或逆序时最不适合用快速排序，此时快速排序时间复杂度为O(n^2)，空间复杂度为O(n)

数据量较小时适合用时间复杂度为O(n^2)的排序算法，因为代码简洁便于实现
数据量较大时适合用时间复杂度为O(n\log n)的排序算法，因为性能更好

Reference

堆排序 – 菜鸟教程
冒泡排序 – 菜鸟教程
归并排序 – 菜鸟教程
基数排序 – 菜鸟教程
快速排序 – 菜鸟教程
快速排序 – 维基百科
基数排序 – 维基百科
快速排序算法 – bilibili
Python实现基数排序 – CSDN
【算法】排序算法之归并排序 – 知乎
深入理解快速排序（quciksort） – 知乎
排序算法之 基数排序 及其时间复杂度和空间复杂度 – CSDN