序列长度为$N$，默认目标：从小到大排序
稳定性：排序前后与过程中，相等两个元素的相对顺序不会改变（需注意：有时候实现方式不同，稳定性也不同）
排序成本模型：在研究排序算法的时候，我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数；空间复杂度如果是在原储存空间上即为$O(1)$，额外数组需要计算空间，每一次递归会开辟一个递归栈也需要占用空间。
基本排序算法
冒泡排序
经典
[步骤]：①外层循环：从第1个数到第$N-1$个数
②内层循环：从第1个数到第$N-i-1$个数（$i$为外层循环计数，$N-i$即为待排序序列）开始依次两两比较（$j$与$j+1$比，$j$为内存循环计数），若遇到前者大于后者，则两两交换顺序
[核心]：内层循环设置一一交换相邻两个顺序不对的元素位置，像水泡一样一点点不断向上冒出来，每一轮外层大循环可以冒出一个最大的元素，加入已排序序列。
[特性分析]：①稳定（相同相邻元素不交换，交换只发生在相邻元素）
[复杂度]：①时间：两层循环，最坏情况是完全反序，每两个相邻的都交换一次，比较$(N-1)+\cdots+1+2=\frac{N(N-1)}{2}$次，交换最$\frac{N(N-1)}{2}$次；最好的情况是已经有序，只需进行一轮冒泡就发现已经有序（设置一个本轮未发生交换的flag），此时比较了$N-1$次。平均时间复杂度为$O(N^2)$
②空间：原地in-place，$O(1)$
选择排序
[步骤]：①每一个大循环找到待排序序列中最小的元素 ②将其与待排序序列第一位交换，当前待排序序列第一位及左边元素即为该轮新的已排序序列
[核心]：不断地选择待排序序列中的最小者，放置到已排序序列末尾
[特性分析]：①复杂度与初始顺序无关（上一遍的扫描不能为下一步提供任何信息）②数据移动少（交换）③不稳定（将最小者固定放到已排序序列末尾，打乱了相等元素的顺序；④每个时刻生成的已排序序列是最终序列的子序列，
举例，某一轮排序：| 5(1) 5(2) 3->3 | 5(2) 5(1))
[复杂度]：①时间：两层循环，$\frac{N(N-1)}{2}≈\frac{N^2}{2}$次比较，$N$次交换，增长级为$O(N^2)$
②空间：in-place（同一个序列内部排序，并划分为已排序部分和未排序部分，无需外部储存），空间复杂度为$O(1)$
[改进]：将内层循环中的交换改为将较大元素都向右移动
插入排序
[步骤]：①每一个大循环顺序从待排序序列里取一个元素②将其插入进已排序序列里的正确位置（在已排序序列中找到第一个前者小于该数后者大于该数的位置，插入，后面的已排序序列依次右移一位）
[核心]：顺序循环待排序序列中的每一个元素，将按正确顺序插入进已排序序列中
[特性分析]：①复杂度与初始顺序有关（基本有序序列比完全无序序列快很多，所以基本/部分有序序列使用效果非常好）②稳定（可设定未排序序列中的相等元素始终被插入已排序序列中相等元素的后面） ③每个时刻生成的已排序序列不是最终序列的子序列④不适合大规模数据，因为每一次的插入都伴随大规模的数组移动（数组）
[复杂度]：①时间：两层循环，最坏情况（完全逆序）需要$\frac{N^2}{2}$次比较和交换；最好情况（完全有序）需要$N-1$次比较和$0$次交换；平均需要$\frac{N^2}{4}$次比较和交换；增长级见后图（为比较次数去掉常数参数项）
②空间：in-place（同一个序列内部排序，并划分为已排序部分和未排序部分，无需外部储存），空间复杂度为$O(1)$
希尔排序
基于插入排序
[步骤]：①外层大循环，每一轮选取一个GAP大小（设定每一轮$GAP\to GAP/h$）②序列中所有间隔$GAP$距离的元素为一个GAP分组，对每个分组进行插入排序 ③直到GAP缩小到1，此时最后一轮相当于对整个序列进行插入排序
[核心]：改进了插入排序的缺点：越无序，数组越长，时间越长。通过巧妙分组，局部排序，每一次插入排序的数组仅限于一个GAP内，数量少；每经过一轮，序列逐渐局部有序，虽GAP逐渐缩小导致每个分组内元素逐渐变多，但是插入排序对基本有序序列排序具有很大优势，巧妙利用了插入排序的优势。
[特性分析]：①复杂度与初始顺序有关、每个时刻生成的已排序序列不是最终序列的子序列（毕竟基于插排） ②不稳定（gap子插排的存在）③希尔排序比插入排序和选择排序要快得多，且数组越大，优势越大
[复杂度]：略
基于分治思想的排序算法
归并排序
一种分治算法
[步骤]：
分（归）：两种归并的方法，区别在于归并顺序不同
可以用一个二叉树来表示所有的比较子问题，其中每个结点代表访问一个子问题（实际上所有递归比较问题都可以这么等效，包括下面的快速排序）
①自顶向下（递归）
开始递归，将问题划分为左边序列和右边序列两个子问题，先考虑左边子问题，出栈的时候开始执行并操作
递归的顺序：先左，依次入递归栈，直到抵达最小子问题，进入并流程，最底层递归出栈，再右，如此往复层层进栈出栈，每出一次栈解决一个子问题。
类似于二叉树的深度遍历
②自底向上（多次遍历整个序列）
先将问题（整个序列）全部划分为最小子问题（长度为2或3的序列），然后进行两两归并，然后四四归并，然后八八归并，直到全部归并完毕。
类似于二叉树从底部开始的层次遍历
治（并）：如何处理一个子问题（即如何“并”：将两个有序序列合并为一个有序序列）
开辟一个temp数组，依次比较左边序列和右边序列的第一个元素，若左边的小就先将左边第一位元素插入temp中，若右边的小就先将右边第一位元素插入temp中，插入后该序列左移排除空位，继续比较。若某一边元素全部已插入，那么另一边子序列的剩余元素全部直接插入temp末尾。
[核心]：归并排序是分治思想的典型应用。将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。
「分」而「治」之——「归」而「并」之——归并：
①分：归：将序列排序问题套娃划分成短序列排序的子问题
②治：并：将子问题采用并入中间数组的方式进行排序
分而治之，为什么分了之后“治”子问题的时候采用并入的方式排序会高效？因为这里利用了并的时候两边子序列是有序的特性，这样每并入一个元素的时候只需要比较左边序列第一个和右边序列第一个谁大谁小即可，且当某一边最大元素小于另一边的时候，剩下的元素直接copy，所以对两边都有序的子序列求并的运算复杂度很低
对于并过程中的短序列，也可以使用插入排序解决（可能比直接并更快）
[特性分析]：①当数组长度为2的幂时，自顶向下和自底向上的归并顺序所用的比较次数和数组访问次数正好相同，只是顺序不同。②稳定（相等元素不会被交换先后位置）
[复杂度]：分析归并算法的时间复杂度，实际上就是分析递归算法复杂度。
①时间：比较模型为二叉树，那么可以直接计算出：$x$为递归次数（子问题个数），$2^x=N,\therefore x=\log N$，每个子问题即为进行一次合并，需要用时$1到N$之间，那么归并排序的时间复杂度增长极即为：$子问题个数×合并时间=O(N\log N)$
②空间：out-place，除原数组外需要一个“并”数组储存空间，用于并的时候做临时“并”用，再拷贝回原数组。其长度为$N$；又因为递归栈的深度为$\log N$，所以空间复杂度为$O(N)+O(\log N)=O(N)$
（归并排序可多线程）
快速排序
一种分治算法，与归并排序互补，也是基于递归，存在递归调用二叉树。
[步骤]：
分：
①开始前先随机打乱序列 ②开始递归，随机选择一个元素作为切分元素（默认选序列第一个元素） ③每次递归选择一个切分点将序列划分为两个子序列，将随机选定的切分元素交换到切分点位置上，左边序列所有元素都小于切分点，右边序列所有元素都大于切分点 ④按照先左后右，与深度遍历二叉树一样的顺序继续递归左右子序列，不断获得切分点，得到最终序列
治：每个子问题③中如何选择切分点（荷兰国旗问题）
从子序列最左设定指针$i$，指向的元素为$a[i]$；子序列最右设定指针$j$，指向的元素为$a[j]$，随机选定的切分元素为$v$。
先$i$不断右移，直到找到一个$a[i]>v$；然后$j$不断左移，直到找到一个$a[j]<v$；将$a[i]和a[j]$交换，继续重复先后移动指针$i,j$。如果在$i或j$移动过程中相遇了，即$i==j$，则将切分元素和相遇处元素$a[j]$交换，作为切分点。（具体实现可以不这样，有更好的基于直接赋值的实现方式）
直到两个指针相遇，该点即为切分点，再将切分元素和切分点上的元素交换。
[核心]：基于分治算法。
分：每次递归计算一个切分点，将序列排序问题套娃切分成短序列排序的子问题
治：如何计算这个切分点：确保切分点后的子序列所有数大于切分点前所有数
[特性分析]：①每一次切分过程总是能排定一个元素，处于最终位置，不会再改变 ②序列越随机，效果越好，最好的情况是每次切分点正好是将子序列对半平分；最坏的情况是序列是已经排好的序列，一次切分只确定了第一个数，下一次切分的子序列只比上一个子序列少1（即上一个问题确定的切分点），子问题很大。所以我们首先将数组随机打散，避免了最坏情况③不稳定（比如 2 2 1 4 7 8，走一遍流程就看出来）④对于小数组，快速排序比插入排序慢（看增长级图）
[复杂度]：
①时间：$x$为递归次数（子问题个数），问题模型为二叉树，最好情况下是每次切分点正好将子序列对半平分，即体现为完全二叉树，则子问题个数大约为：$2^x=N,\therefore x=\log N$；最坏的情况是序列是已经排好的序列，每个子问题只确定了一个数的正确位置，则子问题个数为$N$；治中交换的成本增长级为$N$。
递归时间复杂度=递归次数（子问题个数）×子问题处理时间。所以时间复杂度为：最坏$O(N^2)$，最好$O(N\log N)$，平均$O(N\log N)$
②空间：数组储存空间是原地的：in-place，复杂度为$O(1)$；递归栈需要空间，所以快排的空间消耗只由递归栈的深度决定，最好情况深度为$\log N$，平均$O(\log N)$，最坏$O(N)$，分析方法同时间
[与归并排序的区别]：在归并排序中，先递归，再处理子序列（merge）；而在快速排序中，先处理子序列（荷兰国旗问题），再递归。不过两种算法的“处理子序列”含义是不一样的，在归并排序中是将子序列完全排序，而在快速排序中，是确保切分点后的子序列所有数大于切分点前所有数，并不要求完全排序
[改进]：
①在排序小数组子问题中切换到插入排序，结束该分支下的递归
②三取样切分：找序列的中位数点一分为二，再找子序列中为数点一分为二，再找一次一分为二，共做三次中位数划分，分别对划分出的子序列做快速排序，最后再做插入排序
③三向切分：针对存在大量重复元素的序列，其时间复杂度降低到线性级别$O(N)$【略】
堆排序
[核心]：
堆的数组存储方式中，完全是按照完全二叉树的序号顺序存储的，对于父节点序号parent，左子节点序号为2*parent+1，右子节点序号为2*parent+2，序号最大的父节点序号为(lastindex-1)/2
几个核心动作：
①一次调整(adjust)：一次调整是一个循环过程。从parent节点子树往下进行调整（直到尾节点），如果不满足条件则子节点与父节点交换(swap)，并继续调整子节点，直到满足条件则停止继续往下调整，跳出循环。注意：从序号最大的parent开始，对每个节点进行调整！！！遍历范围: parent~((length-1)-1)/2
②建堆(build)：从序号最大的父节点开始向上进行多次调整(adjust)
③堆排序(heap sort)：建堆(build)，然后每次取堆顶与堆尾进行交换(swap)，然后对堆顶进行一次调整(adjust)
[数据结构]：优先队列两大基本操作：①删除最大元素②插入元素。
二叉树 简称 堆。大根堆：二叉树上的每个子树的父节点大于两个子节点；小根堆：二叉树上的每个子树的父节点小于两个子节点。（注意理解“子树”的含义，所有的递归套娃子树都要满足这个条件）
完全二叉树可以用数组实现，即二叉堆：一组能够用堆有序的完全二叉树排序的元素，并在数组中按层级储存（不使用数组中的第一个位置）
堆排序即是将无序堆通过上浮转化为大根堆，或通过下沉转化为小根堆，的堆有序化过程，是一种基于堆的优先序列实现。
[步骤]：
用[二叉堆数组]实现，且使用遍历算法（无需递归）
关键步骤
①建堆（从最右子树父节点开始调整，一直调整到根节点）
②堆排序（不断交换根节点与已排序区指针位置，调整根节点（array[0]））堆排序过程中维持一个不断扩大的已排序区，堆区域则一直在缩小（0,lastindex)
关键过程：
调整（若本节点孩子不符合规则，则调整完该结点继续调整孩子结点，即遍历调整该结点，直到不需要调整或到叶子结点）
[核心]：每取出一个最大/最小的数，堆就进行一次有序化
[特性分析]：①适合在大量数据中，找序列中前几个最大/小的元素 ②不稳定
[复杂度]：①时间：树的深度最深为$\log N$，每上浮/下沉一个数需要耗时的数量级则为$O(\log N)$，一共有$N$个数，则全部排序需要耗时数量级为$O(N\log N)$
②空间：不需要递归，不需要额外空间，in-place，只在堆数组上进行，则时间复杂度为$O(1)$
基于区间划分思想的排序算法
计数排序
将数字铺到一个数组里
空间浪费
非比较的
桶排序
划分多个范围相同的区间，每个自区间自排序，最后合并（merge）。
桶排序(Bucket Sort)假设输入数据服从均匀分布，然后将输入数据均匀地分配到有限数量的桶中，然后对每个桶再分别排序（可以使用任何排序算法），对每个桶再使用插入排序算法（merge），合并方法同归并的merge。最后将每个桶中的数据有序的组合起来。假设输入是由一个随机过程生成，该过程将元素均匀的分布在一个区间[a,b]上，在[a,b]之间放置一定数量的桶，由于桶排序和计数排序一样均对输入的数据进行了某些假设限制，因此比一般的基于比较的排序算法复杂度低。
基数排序
按照基数分桶，比如是十进制排序，则每一位是0~9，那么就分为10个桶
每一轮循环排序一个位，排序的时候储存在桶中，然后再复制回原数组
这样对每一位经过若干轮之后，最后的原数组即为最终排序数组
复杂度显然是基数（外层循环）×元素个数（内层循环）
注意是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
https://www.runoob.com/w3cnote/radix-sort.html
总结
关于归并排序与快速排序空间复杂度问题：
归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是O（n）。
而快速排序每次递归都会返回一个中间值的位置，必须使用栈。所以空间复杂度就是栈用的空间。
可以画出增长级图来根据数据量选择合适的算法，但也要考虑其它特殊因素，比如插入排序对基本有序数列非常快等等特性
