排序
直接插入排序
即将每个元素一次插入到有序的部分
一开始将第一个数作为有序区
直接插入排序即按顺序对每个元素与有序区的最后一个元素比较，若比其小（默认升序），则将该元素存入temp，让temp和有序区的各个元素比较，决定插入位置，插入后有序区扩充
我们采取倒着比较，可以实现同时比较与移动
时间复杂度：\(O(n)\)(最好), \(O(n^2)\)(最坏)， \(O(n^2)\)(平均)
空间复杂度：\(O(1)\)(辅助空间)
稳定性：稳定排序
折半插入排序
区别：找插入位置的方法改为了折半查找
每次将待插入元素放入temp，让left与right指向有序区首尾，通过二分找到合适的插入位置
- 时间复杂度：\(O(n)\)(最好), \(O(n^2)\)(最坏)， \(O(n^2)\)(平均)
- 空间复杂度：\(O(1)\)(辅助空间)
- 稳定性：稳定排序
希尔排序
基于插入排序的优势：基本有序与数量较小时的高效率
希尔排序通过增量d来对元素分组，d初始为长度的一半
按增量从下标为0开始，间隔d的元素分成一组，组内进行插入排序，排序完将起始点++，继续按间隔d的元素分成一组，以此类推，这是第一轮
第一轮结束后，将增量减半，继续分组进行插入排序
直到增量取值为1，此时即对整个数组插入排序
- 时间复杂度：\(O(n)\)(最好), \(O(n^2)\)(最坏)， \(O(n^{1.3})\)(平均)
- 空间复杂度：\(O(1)\)(辅助空间)
- 稳定性：不稳定排序
冒泡排序
即每轮都从前往后比较相邻的两个，逆序就交换
直到不能移动即实现归位，排好了一个元素
改进：引入flag标记每一轮是否进行交换，若发生交换则改为true，每轮结束后判断是否为false，若为false则表示已经有序
- 时间复杂度：\(O(n)\)(最好), \(O(n^2)\)(最坏)， \(O(n^{2})\)(平均)
- 空间复杂度：\(O(1)\)(辅助空间)
- 稳定性：稳定排序
快速排序
任取元素作为枢轴，划分成小于枢轴与大于枢轴两个部分，然后递归处理左右，直到空或只剩一个，以取第一个为例
定义一个pivot变量，将枢轴元素存入，设left与right指向数组首位，先让right向左移动，每个元素与枢轴比较，若小则移动到left位置，否则继续右移；然后让left向右移动，与枢轴比较，若大于则移动到right位置，否则继续右移
也可以不用pivot变量，而直接swap
即：
right从右往左找比枢轴小的元素去填left的坑
left从左往右找比枢轴大的元素去填right的坑
当left==right时，第一次划分结束，划分出两个区间，将枢轴填入指向的坑，此时枢轴归位
然后递归的处理每个区间
- 时间复杂度：\(O(n\log n)\)(最好) \(O(n^2)\)(最坏)， \(O(n\log n)\)(平均)
- 空间复杂度：\(O(\log n)\)(辅助空间 最好), \(O(n)\)(辅助空间 最差), \(O(\log n )\)(辅助空间 平均)
- 稳定性：不稳定排序
简单选择排序
即每轮在剩下的数里选最小的换到前面
定义一个k变量，保存最小值下标，每轮设为剩下元素中的第一个位置，从下标1开始依次和k中下标变量比较，并更新最小元素下标，搜索一趟后，找到最小值位置，与下标0的元素交换，此时该位置元素归位
- 时间复杂度：\(O(n^2)\)(最好) \(O(n^2)\)(最坏)， \(O(n^2)\)(平均)
- 空间复杂度：\(O(1)\)(辅助空间)
- 稳定性：不稳定排序
堆排序
堆排序是使用堆实现的
建堆：倒着将每个节点为根的子树调整成堆，可以直接从非叶子节点开始调整
寻找最后一个非叶子节点，即第\(\lfloor \frac{n}{2}\rfloor\)号节点（第n号节点是最后一个叶子节点），拿其与其子树比较，判断是否为堆，若不是则交换不符合的父子节点
交换后，若子树非叶子节点，则需要继续往下比较，防止已有结构被破坏
（即从最后一个非叶节点开始依次向下调整）
排序：每次将堆顶元素与最后一个元素做交换，然后向下调整新的堆顶，此时该元素归位，隐去
- 时间复杂度：\(O(n\log n)\)(最好) \(O(n\log n)\)(最坏)， \(O(n\log n)\)(平均)
- 空间复杂度：\(O(1)\)(辅助空间)
- 稳定性：不稳定排序
归并排序
将两个有序数组合并为一个
取两个指针指向两个数组的开头，比较更小的放入新数组并移动指针
其中一个放完后，另一个剩下的元素直接放到最后
非递归
归并排序即每轮堆相邻的子序列两两归并
一开始把每个元素作为单独子序列，此时所有序列均有序，之后开始归并，归并方法按照上文
一轮归并完后再进行归并，直到变成一个序列
递归
从自顶向下思考
首先通过左右端点下标确定中间位置，根据中间位置划分为两个区间，
递归左右区间，通过中间位置划分为两个区间，再递归左右区间
直到两个区间有序，则回溯并执行归并操作
- 时间复杂度：\(O(n\log n)\)(最好) \(O(n\log n)\)(最坏)， \(O(n\log n)\)(平均)
- 空间复杂度：\(O(n)\)(辅助空间)
- 稳定性：稳定排序
基数排序
这是一种非比较排序，进行逐位排序
首先统一各元素位数，不够的加前导零
按照从最高位和从最低位排序，分为LSD（最低位优先）与MSD（最高位优先）
LSD较为简单：
首先将所有数按照个位分配，对于十进制，基数为0-9，造十个桶来存储，把每个数按照个位放到对应桶里
这里的桶采用链式存储，满足先进先出，即队列
然后从小到大遍历每个桶，把元素取出并链起来（next指针指向每个桶的队头）
然后按照十位分配，操作同上，直到整体有序
- 时间复杂度：\(O(d\times (n+r))\)，其中d为最大数位数，n为要排的n个数，r为基数
- 空间复杂度：\(O(r)\)(辅助空间)
- 稳定性：稳定排序