1.排序算法的稳定性

算法名称	时间复杂度	时间复杂度	算法种类	是否稳定	原因
冒泡排序	$O({N}^{2})$	$O(1)$	基于比较	稳定	在冒泡的时候，如果遇到前后相同的值两者不交换即可，只有前者比后者大才交换；
插入排序	$O({N}^{2})$ 最好情况$O(N)$	$O(1)$	基于比较	稳定	同样在比较的时候，相同的值不交换即可；
选择排序	$O({N}^{2})$	$O(1)$	基于比较	不稳定	因为如果后面有小于前面的，就和前面的互换，如果有几个相同数，则相当于和最前面的数进行互换，这样顺序就乱了；
归并排序	$O(N * log_{2}^{N})$	$O(N)$	基于比较	稳定	以为归并之前是左右两个数组，左边数组在原数组中就是在左边，右边数组原来就是右边，这样只需要如果左右两个数组中有相同的数字，则只需要先拷贝左边数组值，然后拷贝右边数组中值即可；
快速排序	$O(N * log_{2}^{N})$	$O(N)$	基于比较	不稳定（也可以稳定）	因为 partition 过程就是交换，肯定是无序的；
堆排序	$O(N * log_{2}^{N})$	O(1)	基于比较	不稳定	因为在形成大根堆的时候，叶子结点与根节点进行交换的时候就会序号乱，例如：2,2,3；当放入 3 的时候，两个 2 的顺序就改变了；
桶排序	$O(N)$		非基于比较	稳定
基数排序	$O(N)$		非基于比较	稳定
计数排序	$O(N)$		非基于比较	稳定

排序问题补充：

归并排序的空间复杂度可以变成 O(1)，可以采用 “归并排序内部缓存法”实现，但是仅仅要求了解即可；
快速排序可以做到稳定性，采用“01 stable sort”；
荷兰国旗问题不可能稳定，因为明显存在交换；问题：将一个数组的奇数放在数组左边，偶数放在数组右边，并且要求原始的相对次序不变，时间复杂度要求：O(N)，空间复杂度要求：O(1)； 解析： 因为每一个数不是奇数就是偶数，因此也是可以抽象为一个 0 1 问题，相当于把 0 类（例如 < 0.5 的，这里 0.5 是随便取，就是为了区分）的放在左边，把大于 0.5 的放在右边，即 1 类；且保证原来的相对顺序不变，抽象就是快排的 partition 过程保证稳定；因为 partition 过程就是将一个数组分为 <= 和 > 两个部分，也是 0 1 过程，如果上述满足就可以实现快排稳定；只能采用 01 stable sort 解决；

2.认识比较器

比较器作用：自己实现比较自己定义的对象的方法，然后通过将其传入系统中有序的结构就可以处理自己定义类型的比较；就是自己只需要实现自定义比较规则

例如：使用优先级队列（实质上就是堆）存放自定义对象，然后自定义比较器使得可以比较自定义的类型对象；

3.桶排序

桶排序仅仅是一种概念，整体思想是首先记录数据各状况出现的词频，然后根据词频进行还原从而达到排序目的；它的具体实现有：计数排序、基数排序；

4.计数排序

有多少个元素就需要多少个桶； 示例：有一个元素值范围为：0 ~ N 的数组，将其排序；步骤：首先准备一个长度为 N + 1 (数组最大值 + 1 )的辅助数组；辅助数组下标分别为：0 ~ N；然后遍历原数组，有一个 X 值（大小位于 0~N 之间），就在辅助数组下标为 X 的对应元素值 + 1；一直遍历结束；最后将辅助数组中各个下标对应的元素值还原，示例：辅助数组为：[1,2,0,2]就相当于有 1 个 0,2 个 1,0 个 3,2 个 4，因此结果为：[0,1,1,4,4]；

package cn.test;

import java.util.Arrays;

/**
 * @Author smallmartial
 * @Date 2020/2/29
 * @Email [email protected]
 */
public class BucketSort {
    private static final int WITHOUT_SORT_LENGTH = 2;

    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //首先找到排序的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        //新建一个max + 1个桶，然后遍历数组，如果数组为x,则桶的位置为 x+1;
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0){
                arr[i++] = j;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {0,5,2,1};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

5.基数排序

补充示例： 给定一个数组，求如果排序之后相邻两个元素的最大差值，要求时间复杂度为 O(N)，且不能用非基于比较的排序； 解答：

思想：借用桶的思想，但是不使用桶排序；
思路：
- 准备桶，原数组中有 N 个元素，因此准备 N+1 个桶；
- 遍历原数组，找到原数组中的最小值和最大值，分别放在第 0 号桶和第 N 号桶中；如果最大值等于最小值，直接返回 0 结束；
- 将新数组（桶）的 0 ~ N 部分等分为 N+ 1 份，原数组中值属于哪一个部分就放在哪一个桶中；示例：如果原数组一共 9 个数，则准备 10 个桶，且第一个桶中放的是数组最小值 0（假定），最后一个桶放的是最大值 99（假定），则将 0 ~ 99 等分为 10 份，则原数组中出现 0 ~ 9 直接的数放在 0 号桶，出现 10 ~ 19 之间的数放在 1 号桶。。。；
- 每个桶只保留三个值：一个 Boolean 值，用于判断该桶中是否有元素，一个 min，表示桶中的最小值，一个 max ，表示桶中的最大值；因此如果元素 X 进入 7 号桶，如果 7 号桶之前没有元素，则首先将 Boolean 值置为 true，然后 min = x，max = x；当又一个元素进入 7 号桶的时候，比较桶内元素的值，更新最大值和最小值，其他值扔掉；
- 最后遍历所有的桶，如果遇到空桶，跳到下一个进行判断，如果是非空桶，找到其左边最近的非空桶，将后一个非空的 min - 前一个非空的 max，插值进行保存，然后比较所有的插值，取最大的就是最大插值，
原理：因为 0 号桶非空，N 号桶非空，但是只有 N 个数，因此中间至少有一个桶是空的，同时任何两个相邻的数可以来自于同一个桶，也可能来自于不同的桶；
- 为什么要设置一个空桶：因为至少有一个桶为空，则距离空桶左右最近的两个非空桶：左非空 min .... 左非空 max 。。。空桶。。。右非空 min....右非空 max，则右非空 min - 左非空 max 的插值一定大于桶内插值，因为其值至少是一个桶的长度，而同一个桶内元素之间的插值是不会大于桶长的，为了证明：最大的插值一定不会来自于同一个桶。但是空桶仅仅是用于否定最终答案不是在同一个桶中，但是不是答案一定就是在空桶的两边；示例：非空：13,19；空；非空：30，39；非空：59,63；不是空桶左右俩个的插值最大；

package cn.test;

/**
 * @Author smallmartial
 * @Date 2020/2/29
 * @Email [email protected]
 */
public class MaxGap {
    private static final int WITHOUT_SORT_LENGTH = 2;
    public static int maxGap(int[] nums) {
        if (nums == null || nums.length < WITHOUT_SORT_LENGTH) {
            return 0;
        }
        int len = nums.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 找到数组中的最大值和最小值
        for (int i = 0; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        if (min == max) {
            return 0;
        }
        // 下面三个数组是描述 len + 1 个桶中每个桶的三个必备信息
        boolean[] hasNum = new boolean[len + 1];
        int[] maxs = new int[len + 1];
        int[] mins = new int[len + 1];
        int bid = 0;
        for (int i = 0; i < len; i++) {
            // 确定该数去第几号桶
            bid = bucket(nums[i], len, min, max);
            // 该桶中的三个信息进行更新
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
            hasNum[bid] = true;
        }
        // 找到每一个非空桶和离他最近的非空桶的插值：用当前min - 前一个max；
        int res = 0;
        int lastMax = maxs[0];
        int i = 1;
        for (; i <= len; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    public static int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }
}

6.工程中的综合排序算法

首先会判断数组的长度（一般界限为 60）；
- 如果数组长度较短，一般使用插入排序，虽然插入排序的时间复杂度为：$O({N}^{2})$ 但是因为数据量较小，因此 $O({N}^{2})$ 比 $log_{2}^{N}$不会差距很大，但是因为插入排序的常数项很低，因此整体的时间复杂度较低；
- 如果数组长度较长
  - 首先判断数组中装的数据类型
    - 如果是基础数据类型：使用快排，因为其相同值没有区分，因此不必考虑稳定性；
    - 如果是自定义数据类型：使用归并排序，因为即使相同值也是有区别的，要保证稳定性；
  - 然后如果使用快排的话，因为快排使用分治划分的思想，因此在递归的时候如果划分多次之后数组长度减少到一定长度（例如 60），则直接使用插入排序；