为所有算法提供了保证稳定的解决方案
迭代与递归转换
数组与链表
排序的性质
在位：使用的额外内存，是否分配了新数组
稳定：相同元素不改变原有相对位置。可以把原下标作为第二关键字，先按key（第一关键字），再按index（第二关键字）排序，最终结果稳定（但是存在相同元素错位的中间过程）
从算法结果判断算法是否为稳定：与稳定排序算法的排序结果与数组比较，也需要额外标记，不如直接遍历一次，检查相同元素的第二关键字是否有序。
输入数据的特征对算法的影响
插入排序
分解一次插入动作：
A[i]=temp
1.在左方已排序数组（0，i-1）中搜索刚好大于A[i]的元素A[k]
2.向右移动数组（k,i-1）
3.插入元素A[k-1]=temp
优化：用二分搜索替代遍历搜索，但是会影响最优情况（已排序数组）的复杂度
很多算法会把搜索与移动元素的动作耦合在一起，
从后向前遍历搜索，这样对数组成员只需要访问一次，但是不能用二分加快搜索
从后向前遍历搜索也保证了算法稳定
优点：自适应已排序的情况，便利一次结束算法
在位：不需要额外数组
稳定：保证插入位置——插入元素的右方元素大于它（如果等于，则不稳定）
插排：考察元素间的相对次序，而不试图找到绝对位置
选择排序
1.选择剩余未排序数组中的最大/最小统计量
2.交换（不稳定）
另一种思路（保持稳定性）
2.移动数组
3.插入
冒泡排序
与选择算法原理思路2是一致的，每次找到的是第k统计量
冒泡动作其实是移动数组动作的分解
算法提前结束标志：一次遍历没发生交换动作
归并排序
递归，最终从小数组到大数组依次合并
稳定：对于相同元素，定义左边数组的元素优先级高
在位：合并动作需要额外的数组
子问题：合并数组
优化：不需要两个数组都复制，复制左边的就可以了。如果进一步优化空间，可以分配两者短长者的数组长度，但会造成移动数组的开销
所以空间复杂度为n
快速排序
子问题：分割（可用于找到前k统计量（无序））
分割交换：
方案1：交换（选排中也出现）：不稳定
方案2：移动数组：稳定
避免移动数组造成的复杂度：使用额外数组，保留大于划分的数，划分结束时赋值回原数组
空间复杂度nlogn
如果维护后段数组的偏移量，并在算法结束时计算绝对位置，每个数最多一次赋值回原数组
一次迭代完成，左部分偏移量+0，右部分偏移量+1
随迭代进行偏移量增加
绝对位置=相对位置+总偏移量
计数排序
B[value]=num
其他优化：快排中小数组利用插排减少函数调用开销,合并排序亦可做此优化。
基于比较的算法复杂度下界为nlogn
构造一个算法，数组从1个元素开始
每加入一个元素，在数组中二分查找插入位置
则最后一个元素插入的比较次数为logn-1
比较次数之和all（logn）