第三篇，插入排序算法：直接插入排序、希尔排序
此为第三篇，插入排序算法：直接插入排序、希尔排序。
简介
插入排序是一种简单直观的排序方法，其基本思想是：每次将一个待排序的记录按其关键字大小插入到前面己排好序的子序列中，直到全部记录插入完成。
基于插入的排序算法主要介绍直接插入排序和希尔排序。
一.直接插入排序
假设在排序过程中，待排序表 L[1....n]在某次排序过程中的某一时刻状态如下：
要将元素L(i)插入到已有序的子序列 L[1....i-1]中，需要执行以下操作（为避免混淆，下面用L[] 表示一个表，而L() 表示一个元素）
(1) 查找出L(i) 在 L[1....i-1] 中的插入位置 k
(2) 将 L[k... .i-1] 中的所有元素依次后移一个位置
(3) 将 L(i) 复制到 L(k)
为了实现对 L[1....n] 的排序，可以将 L(2)~L(n) 依次插入到前面已排好序的子序列中，初始L[1] 可以视为是一个已排好序的子序列。上述操作执行 n-1 次就能得到一个有序表。插入排序在实现上通常采用就地排序（空间复杂度O(1)），因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。
假定初始序列为 49, 38, 65 , 97 ,76, 13, 27, 49 ，初始时 49 可以视为一个己排好序的子序列，排序过程如下图所示：
1.例程
/********************************* 直接插入排序（插入排序） *********************************/#include <stdio.h>#include <stdlib.h>#include <string.h>void InsertSort(int *data, int length){int i, j, temp;for(i = 1; i < length; i++) //从序号1开始进行循环if(data[i] < data[i-1]) //若后面比前面小，则将小的插入前面的有序表{temp = data[i]; //复制为哨兵for(j = i-1; j >= 0 && temp < data[j]; j--) //从后往前查找待插入位置data[j+1] = data[j]; //向后挪位data[j+1] = temp; //将哨兵复制到插入位置}}int main() {int i = 0;int data[] = {23, 64, 24, 12, 9, 16, 53, 57};int temp[] = {0};int length = sizeof(data) / sizeof(int);InsertSort(data, length);for (i = 0;i < length;i ++) {printf("%4d", data[i]);}printf("\n");}
2.性能分析
2.1适用性
适用于顺序存储和链式存储的线性表（而大部分排序算法都仅适用于顺序存储的线性表）。为链式存储时，可以从前往后查找指定元素的位置。
2.2空间复杂度
仅使用常数个辅助单元，故空间效率为：O(1);
2.3时间复杂度
排序过程中，向有序子表中逐个地插入元素的操作进行了 n-1 趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。
在最好情况下，表元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。
在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，为 2+3+....+n，总的移动次数也达到最大，为 (2+1)+(3+1)+....+(n+1)。考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 n2/4。
因此直接插入排序算法的时间复杂度为 O(n2)。
2.4稳定性
由于每次插入元素，总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
二.希尔排序
从前面的分析可知，直接插入排序算法的时间复杂度为 O(n2），但若待排序列为“正序”时， 其时间复杂度可提高至O(n)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。
希尔排序的基本思想是：先将待排序表分割成若干形如L [i, i + d, i + 2d,……, i + kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序的过程如下：先取一个小于n的步长d1 ，把表中的全部记录分成d1组，所有距离为d1 的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个步长d2<d1，重复上述过程，直到所取到的 d1 = 1，即所有记录己放在同一组中，再进行直接插入排序，由于此时已具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列，希尔提出的方法是 d1 = n/2, di+1 = Li/2，并且最后一个增量等于1。
若以表{49, 38, 65, 97, 76, 13, 27, 49, 55, 04}为例，第一趟取增量d1 = 5，将该序列分成5个子序列，分别对各子序列进行直接插入排序；第一趟取增量d2 = 3，分别对3个子序列进行直接插入排序；最后对整个序列进行一趟直接插入排序。整个排序过程如下图所示：
1.例程
/********************************* 希尔排序（插入排序） *********************************/#include <stdio.h>#include <stdlib.h>#include <string.h>int shell_sort(int *data, int length) {int gap = 0;int i = 0, j = 0;int temp;for (gap = length / 2;gap >= 1; gap /= 2) { //每次的步长 = 上一次/2for (i = gap;i < length;i ++) { //从gap到length每个比较/* 和插入排序基本一样，只不过插入的gap=1刚开始 temp=data[6], j=i-gap=0若 temp<data[0], 则data[j+gap=6]=data[0], j=j-gap=-6, 跳出循环， data[j+gap=0] = temp若 temp>=data[0],则跳出循环， data[j+gap=6]=temp 即无变换 */temp = data[i];for (j = i-gap; j >= 0 && temp < data[j]; j = j - gap) {data[j+gap] = data[j];}data[j+gap] = temp;}}return 0;}int main() {int i = 0;int data[] = {23, 64, 24, 12, 9, 16, 53, 57};int temp[] = {0};int length = sizeof(data) / sizeof(int);shell_sort(data, length);for (i = 0;i < length;i ++) {printf("%4d", data[i]);}printf("\n");}
2.性能分析
2,1适用性
仅适用于线性表为顺序存储的情况。
2.2空间复杂度
仅使用常数个辅助单元，故空间效率为：O(1);
2.3时间复杂度
由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难，所以时间复杂度分析比较难。当n在某个特定范围时，希尔排序的时间复杂度约为 O(n1.3) ，在最坏情况下希尔排序的时间复杂度为 O(n2)。
2.4稳定性
当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序。例如例子中的49和49。
因希尔排序是不稳定的排序方法。
下一篇，第四篇，归并排序算法。
参考：
《王道数据结构》