本篇博客的主要内容是插入排序。常用的插入排序方法有直接插入排序、折半插入排序、表插入排序和希尔排序。这里介绍两个，直接插入排序和希尔排序。
在介绍排序算法时，我将从基本思想、实例讲解、代码理解三个方面整理。
【直接插入排序】
1.基本思想
直接插入排序（Straight Insertion Sorting）的基本思想是一次将每个记录插入到一个已排好序的有序表中去，从而得到一个新的、记录数增加1的有序表。
2.具体做法
我们把第一个序列元素看成是已经排好序的一个记录，后面的元素依次与已排好序的序列中的最后一个元素进行比较。
3.实例讲解
给序列{23,21,44,35,67,11,87,54}进行排序。
下面是具体比较过程：
21与23比较，序列更新为{21,23,44,35,67,11,87,54}
44与23比较，序列更新为{21,23,44,35,67,11,87,54}
35与44比较，序列更新为{21,23,35,44,67,11,87,54}
67与44比较，序列更新为{21,23,35,44,67,11,87,54}
11与67、44、35、23、21比较，序列更新为{11,21,23,35,44,67,87,54}
87与67比较，序列更新为{11,21,23,35,44,67,87,54}
54与87、67、44比较，序列更新为{11,21,23,35,44,54,67,87}
4.代码理解
看着上面的过程，对于直接插入排序的基本思想也得到了实践证明，心里上似乎明白了这样一种排序方法。但实际上，对于下面的代码，还需要好好理解一番。
直接插入排序算法描述如下：
void StraightInsertSorting(List R,int n) //直接插入排序，定义集合R，序列元素个数n
{ int i,j; //定义整数i、j
for (i=2;i<=n;i++) //i=2,从第二个数开始，与前面的数进行比较，直到最后一个
{ R[0]=R[i]; //将要“进行比较的数”赋值给哨岗R[0]
j=i-1; //找到要进行比较的“前一个数”
while(R[0].key<R[j].key) //当“前一个数”的值大于哨岗的值
{ R[j+1]=R[j]; //则将“前一个数”与该数位置交换
j--; //再继续与前面的数进行比较，直至可以确定该数的位置
}
R[j+1]=R[0]; //否则两个数位置不变
}
}
【希尔排序】
希尔排序，又叫“缩小增量排序”。
1.基本思想
先将整个待排记录序列分割成若干序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
从上述基本思想中可以看出希尔排序与直接插入排序有着紧密联系，希尔排序也是在确立分组后在组内进行一次次的直接插入排序。
2.具体做法
我们需要先确定此个序列的增量序列。先取一个小于序列个数n的整数d1作为第一个增量，把记录分成d1个组，在组内进行直接出入排序，然后取第二个增量d2，重复上述分组和排序工作，直至所取的增量d1=1，即所有的记录放在同一组进行直接插入排序为止。
(一般初次取序列一半为增量，然后每次减半，直到增量为1。)
3.实例讲解
给{48,37,64,96,75,12,26,54}进行排序。
在这里，先确定增量序列为“4,2,1”，具体过程如下：
第一次分组：{48,75}{37,12}{64,26}{96,54}
序列更新为{48,12,26,54,75,37,64,96}
第二次分组：{48,26,75,64}{12,54,37,96}
序列更新为{26,48,64,75,12,37,54,96}
第三次挨个进行直接插入排序：
序列更新为{12,26,37,48,54,64,75,96}
4.代码理解
void shellSort(int data[],int len) //希尔排序，定义数组data[]，数组长度为len
{
int d = len;
int i,j;
while(d > 1)
{
d = (d+1)/2; //确定增量值
for(i = 0;i < len-d;i++)
{
if(data[i+d] < data[i]) //数组的第一个数与间隔增量的数进行比较
{
int temp;
temp = data[i+d];
data[i+d] = data[i];
data[i] = temp; //若间隔增量的数小于前面与之比较的数，则交换
}
for(j = 0;j < 8;j++ )
{
printf("%d,",data[j]);
}
}
}
for(j = 0;j < 8;j++ )
{
printf("%d,",data[j]);
}
}
【总结】 将直接插入排序与希尔排序比较总结后，发现希尔排序本质上其实就是直接插入排序，两者的联系在于希尔排序最后一轮进行的增量为1的排序便是纯粹的直接插入排序；两者的不同在于希尔排序在进行最后一轮之前，经过确定了增量后，便在组内进行直接插入排序，而进行比较的元素间隔便等于增量。 总结完两个排序后，感觉太累，不过这是必须要做的。自考、软考，一遍又一遍，每次都知道了过程是怎样的，但看代码还是困难。所以在软考小组讨论交流的时候，有人提出，直接带数跟着代码走，这样理解更容易，也可以证明自己想的是否正确。这两个排序的代码便是自己通过将实例中的数带进去，一步一步，感觉又有了一些深的理解。
