插入排序(Insertion sorts)专题
这类算法通过在序列内插入并批量移动元素对序列进行排序。
下面介绍的算法实现中，排序输出的结果均是由小到大排列，只要稍微修改下代码（主要是判断语句）都可以使得输出序列的结果由大到小排列。
1.插入排序 Insertion sort
算法(参考维基百科：http://en.wikipedia.org/wiki/Insertion_sort)：
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted
list, and inserts it there. It repeats until no input elements remain.
http://zh.wikipedia.org/wiki/插入排序)：
1.從第一個元素開始，該元素可以認為已經被排序
2.取出下一個元素，在已經排序的元素序列中從後向前掃描
3.如果該元素（已排序）大於新元素，將該元素移到下一位置
4.重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5.將新元素插入到該位置後
6.重複步驟2~5
特点：
1.稳定的(Stability)：相等的两个元素，在执行算法后他们的前后顺序保持不变。
2.比较型排序算法(Comparison)。
3.在线的(Online)：一旦序列末尾接受到新的待排序元素，可以立马将其排序进序列中。(Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array.
It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effect of overwriting the value stored immediately after the sorted sequence
in the array.)
4.原址的(in place)：辅助空间复杂度O(1)，至多需要O(1)空间或内存存储辅助的数据。
5.自适应的(Adaptive)：如果子序列排列是顺序的，算法对新的大序列（含子序列）排序会更高效。
6.时间复杂度：最优：O(n)，此时原始序列已顺序排列；最差：O(n^2)，此时原始序列逆序排列；平均：O(n^2)。
7.数据规模n较大或数据逆序排列时不适用，有更好的其他算法可以代替。插入排序非常适用数据n较小的情况，此时运行时间接近O(n)，并且实现中算法比较比相同时间复杂度的选择排序和冒泡排序要好。
8.在算法从头遍历到尾的过程中，每次执行完后都把前k个元素排列好（对于前k个元素构成的序列而言，而不是整个序列）(As in selection sort, after k passes through the array, the first k elements are in sorted order.)（这一点和交换排序中的地精排序以及选择排序（对整个序列而言也是）很像）。
算法C实现：
void insert_sort(TYPE* array, TYPE count)
{
TYPE i,j, key;
/// check the other elements after the head element.
for (i = 1; i < count; i++) {
/// save the element temp
key = array[i];
/// move the elements one by one.
j = i;
while (j > 0 && key < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
/// insert the element
array[j] = key;
}
}
拓展（参考维基百科）：
针对规模较小的序列插入排序非常高效这一特点，可以与采用分治策略的排序算法结合，典型的运用是将插入排序和快速排序结合：快速排序递归过程中子数组长度小于阈值k时采用插入排序算法（可通过测试确定最佳阈值，可选择k = 8(通常8-20)）（维基百科提到这个结合方式被STL和标准库函数qsort使用，本文在讲解快速排序算法时也有说到这点）。
与选择排序比较：1.算法在遍历序列过程，都逐步让前k个排好序，但是插入排序是局部序列排好，并不是针对整个序列而言，而选择排序确实针对整个序列而言的，但也反应了插入排序的一个优势是它只需扫描前k个元素就可以将k+1个元素排列好，而选择排序必须扫描整个未排序的序列。2.在原始序列排序已经比较好的情况下，由于插入序列通常具有更少的比较次数，因此表现必选择排序更好。3.在读写效率底的平台上，选择排序效率更高( In general,
insertion sort will write to the array O(n^2) times, whereas selection sort will write only O(n) times.)；与此对应的是插入排序的比较次数比选择排序更多。
其他个人想法：选择排序只要遍历时调换下方法，就可以实现从尾部开始进行排序，但是实现交换排序中鸡尾酒排序的双向排序是做不到的。但是改变比较元素之间的距离gap是可行的，运用了和梳排序类似的思想，下面的龟壳排序就是依据这一个思路对插入排序进行了改进。
2.希尔排序 Shell sort
算法(参考维基百科：http://en.wikipedia.org/wiki/Shellsort)：
The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position
faster than a simple nearest neighbor exchange.
插入排序用的比较的元素总是以距离一为单位减小并逐个比较，而希尔排序使用的这里距离gap是变化的，它逐渐减小这个gap并通过对序列进行多次循环从而进行排序。gap由gap sequence获得，这个距离序列的选择非常重要，对希尔排序性能有很大影响。
特点：
1.不稳定的：相等的两个元素，在执行算法后他们的前后顺序可能会发生改变。
2.比较型排序算法(Comparison)。
3.原址的(in place)：辅助空间复杂度O(1)，至多需要O(1)空间或内存存储辅助的数据。
4.自适应的(Adaptive)：如果子序列排列是顺序的，算法对新的大序列（含子序列）排序会更高效。
5.时间复杂度：最优：O(n)，此时原始序列已顺序排列；最差：依赖于gap sequence，已知最好的是O(nlog^2n)；平均：依赖于gap
sequence。（注：时间复杂度具体还是得根据gap sequence序列来求出，维基百科中说的并不明确）
算法C实现：
void shell_sort(TYPE* array, TYPE count)
{
/// set gap sequence
TYPE gaps[8] = {701, 301, 132, 57, 23, 10, 4, 1};
TYPE i, j, k, key, gap;
for (k = 0; k < 8; k++) {
/// get current gap
gap = gaps[k];
/// check the other elements after the first gap element.
for (i = gap; i < count; i++) {
/// save the element temp
key = array[i];
/// move the elements one by one.
j = i;
while (j >= gap && key < array[j - gap]) {
array[j] = array[j - gap];
j -= gap;
}
/// insert the element
array[j] = key;
}
}
}
拓展：
和梳排序一样，通过变化的gap，可以把快速的把序列中距离正确位置较远的元素迅速的排好序，减少因为这类元素而产生的过多的比较和赋值运算时间，这是最值得学习之处。
gap sequence的选择非常重要，维基百科里面举例了很多种类型，也指出了最常用的一种序列(With respect to the average number of comparisons, the best known gap sequences are 1, 4, 10, 23, 57, 132, 301, 701 and similar, with gaps found experimentally.)。