插入排序

简介

基本思想

将一个记录插入到已排序好的有序表中，从而得到一个新的有序表；
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止

分类

1. 直接插入
2. 二分插入

稳定性

相等的插入元素会放在相等元素的后面，所以插入排序是稳定的；
即相等的数据位置不会交换；

直接插入

基本思想

设立哨兵，作为临时存储和判断数组边界之用；

思路1

1. 设置哨兵A为待插入的数据
2. 设置开始查找的位置i
3. 在数组中进行搜索，搜索中将第i个记录后移，直到array[i] <= A；

如果遇到相等的时会造成不稳定

4. 将A插入到array[i+1]位置

思路2

1. 设置哨兵为上次插入的位置为i
2. 比较待插入数据和上次插入数据；如果待插入数据大，则从i向后搜索；如果小，则向前搜索

二分插入

基本思想

对待插入区间进行对折，直到能确定插入位置

思路

1. 计算有序表 0 ~ i 的中间点j，其值为A，用待插入数据B元素与A进行比较，如果B大，则取区间[0, j]；反之，则取区间[j, i]
2. 对取得的区间重复步骤（1）缩小范围，范围依次缩小为 1/2 1/4 1/8 …快速的确定出插入位置
3. 确定位置之后，将之后的序列后移，并将元素插入到相应位置；

希尔排序（缩小增量排序）

基本思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序；

思路

1. 选择一个增量序列，比如d[n/2, n/4, n/8, … 1]，其值n为待排序个数；
2. 先将待排序列按照指定增量d（从第一个增量开始）分成若干组子序列，每组中数据的下标相差d，对组中的全部元素进行直接插入排序（是在原序列中操作的，不会再需要额外空间）；
3. 缩小增量，重复步骤（2），直到d=1；