算法基础及排序
对数器：
用于测试一个方法是否正确（使用一个速记数据生成器生成数据，将数据带入方法测试，以及一个简单的，不管时间复杂度的，正确的，功能一样的方法中得出结果并比较）
递归：
master公式：
用于求子问题为等规模的递归的时间复杂度
T(N)为母问题规模
T(N/b)为子问题的规模，a为子问题被调用次数
O(N^d)除调用子问题之外的进程的时间复杂度
归并排序：
整体为一个递归排序，左右独立有序，再让其整体有序，整体有序国产过程中使用了外排序方法
时间复杂度为O(N*log N)，空间复杂度为O(n)
求小和：
求数组中各个数的左边比它小的数的和
利用归并排序求小和，但是在比较合并时若右边的数小于等于左边的数，则先存右边数组的数
逆序对：
在一个数组中，若一个数比其右边的数大（两数不一定相邻），则组成一个逆序对
快速排序：
荷兰国旗问题：
一个数组，对于一个给定的值，小于这个值的数放到数组左边，等于这个值的数放到数组中间，大于这个值的数放到数组右边
快排1.0：使用数组中最后一个数将数组大于其的数放在数组右边，小于等于的数放在左边，两边进递归，时间复杂度O(n^2)
快排2.0：使用已知数组中最后一个数将大于其的数放在数组右边，等于的数放在中间，小于的数放在左边，大于和小于的数进递归,时间复杂度O(n^2)
快排3.0：在已知数组中随机选一个数，进行划分排序，时间复杂度为O(n*logn)
堆：
size为堆的长度而非数组长度
大根堆：
堆的根节点为所有节点中的最大的数
小根堆：
堆的根节点为所有节点中的最小的数
创建大根堆：
对于大根堆，插入一个值调整代价O(logN)
对于大根堆，若去除最大值之后其余数继续成堆，将堆中最后一个数放于堆的跟，之后令根的左右孩子与根比较，交换完后若其还有子孩子，再继续比较，直到不符合条件（调整代价O(logN)）
index代表从那个位置开始下移
对于大根堆，若随即更改其中一个值，若该值变大则heepInsert上移，反之则heepify下移
调整代价O(logN)
堆排序：
让根与堆中最后一个数做交换，并且heapsize-1，之后对新的根进行heapify下移，之后重复操作，时间复杂度为O(NlogN),额外空间复杂度O(1)（第二张图为更优的建立大根堆方法，可替换第一张图中的for循环）
形成大根堆，可以一个一个加进去，进行heapinsert操作，也可以从下往上，从右往左做heapify操作，后者比前者优，后者复杂度计算：
例题：
可以使用小根堆，取前k+1个数存入小根堆，之后弹出堆根的数，并向后取一个数加入小根堆，直至排序完毕，时间复杂度为O(N*logK)当K相对于数组长度很小，可以认为时间复杂度为O(N)
堆结构注意点：
1.对于堆结构，当容量不够时，就成倍扩容，扩容次数为logN，每次扩容代价O(N)，所以总的代价为O(N*logN)，均摊到每次后代价为O(N)
2.使用系统给的堆结构时，与其沟通方式为add或者poll，若想改变其中一个，代价会很大，若想要对已形成的堆结构中某个数进行操作时，不能使用系统给的堆，需要自己手写
比较器：
对于自己定义的结构，使用系统给的排序函数，无法进行排序，学要自己写下排序的方法，比较器在c++中为重载比较运算符（注释里为书写比较器的规则）
写完比较器，使用系统的排序方法时，把比较器作为参数传过去
比较器还可以用在有序的结构里，如：大根堆，小根堆
在此之前的排序均为基于比较排序
不基于比较的排序（根据数据状况做排序）：
计数排序：
记录每个数的出现次数与该数，时间复杂度为O(N)，此排序仅限于出现的数有一定的范围
基数排序（桶排序）
对于一个数组，确定其中数的最高位，准备10个容器看（编号为0-9）即桶（一般是队列，也可以是栈，数组）从最低位开始一直到最高位，根据该位上个数的数字，放进对应的容器里，结束后根据容器编号从0到9依次将容器里的数放到数组中
基数排序（优化后，思想不变）
创建一个与原数组等长的容器help，创建一个10长度的count数组代替原来的10个容器，使用计数排序的思想，从低位到高位，依次记住出现的频次并依次相加存放，让其变为前缀和数组（此处指的是count数组）原数组从右到左依次片段对应位上出现的数在count作相应查找并存放到help数组的对应位置
count数组，对于i位置上的水k含义为：原数组中对应十进制位上小于等于i的数的数量
代码实现：
排序算法总结：
稳定性指的是相同值的数排完之后还能保证原来的相对次序不变
一般排序选择快排，空间复杂度超出堆排就用，需要稳定就用归并
注意：
基于比较的排序暂时无法做到时间复杂度低于O(N*logN)
基于比较的排序暂时无法做到在空间复杂度低于O(N)的情况下做到稳定
常见的坑：
综合排序：
在样本量大的时候使用快排在调度上时间复杂度低的优势，在小样本情况使用插入的常数极小的优势
对于系统给的arr的sort方法，为什么对于基础类型使用快排，自定义类型使用归并？
因为对于基础数据类型，稳定行没有必要，所以使用常数更小的快排，但是对于自定义类型，系统不知道稳定性是否有用，所以会使用归并