插入类排序的基本思路是在一个已经排好序的子记录上，每一步将下一个待排序的记录插入到已经排好序的记录子集中，直到将所有待排序记录全部插入为止。
1.直接插入排序
直接插入排序是最基本的插入排序算法，它的一趟操作是将第i个记录插入到前面i-1个已经排好序的记录中，在查找记录i的插入位置时，也在进行元素的移动。假设有一个待排序队列r[1,length]，则整个排序过程需要n-1次趟。直接插入算法的实现如下：
void insSort(int *r, int length)
{
int i, j;
printf("Sorting:\n");
for ( i = 2; i <= length; i++) {
r[0] = r[i];
j = i - 1;
while (r[0] < r[j]) {
r[j + 1] = r[j];
j--;
}
r[j + 1] = r[0];
output(r, length);
}
}
具体实现时，用一维数组来存储待排序的序列，其中0号元素备份待插入的记录。
2.折半插入排序
折半插入排序法与直接插入法类似，区别在于确定元素i插入的位置时利用折半查找法。每一趟排序的过程是先用折半查找法确定插入位置，再逐个进行元素的移动。
void binSort(int *r, int length)
{
int i, j;
int low ,high, mid;
printf("Sorting:\n");
for ( i = 2; i <= length; i++) {
r[0] = r[i];
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (r[0] < r[mid])
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= low; j--)
r[j + 1] = r[j];
r[high + 1] = r[0];
output(r, length);
}
}
与直接插入法类似，数组r中的0号元素也备份了待插入的元素i。当确定了记录i的位置时，此时存在low=high+1这样的关系，接下来将low到i-1之间的元素都后移一位，最终记录i刚好插入空出来的位置中。
3.希尔排序
整个希尔排序的过程由若干次希尔插入组成，具体次数由增量数组delta中的元素个数n确定。在每一次的希尔插入算法中，将待排序的记录序列分成d个稀疏子序列，每个稀疏子序列中元素之间的间隔正好为d。希尔插入算法就是将每一个子序列都按照直接插入法排列成有序，从而使得整个序列基本有序。上述过程会重复n次，就是希尔排序算法的整个过程。
void shellSort(int *r, int length, int *delta, int n)
{
int i;
for ( i = 0; i < n; i++) {
shellInsert(r, length, delta[i]);
}
}
第i趟希尔排序中，每个稀疏子序列中元素的间隔由delta[i]决定。但希尔算法的最后一趟排序，元素的间隔必需是1。因为最后一次希尔排序就相当于直接插入排序，但是此时整个记录序列已经几乎有序，因此移动的次数会大大减少。
void shellInsert(int *r, int length, int d)
{
int i, j;
int k;
for (i = 1 + d; i <= length; i++) {
if (r[i] < r[i - d]) {
r[0] = r[i];
for (j = i - d; j > 0 && r[0] < r[j]; j -= d) {
r[j + d] = r[j];
}
r[j + d] = r[0];
}
}
output(r, length);
}
虽然希尔插入算法中需要依次将d个子序列排成有序，但是实际的实现过程却从第一个子序列的第二个记录(d+1)开始依次遍历整个序列，因为每个序列中的元素都是由间隔d控制的，因此就相当于每个子序列各自排序。内部的for循环相当于对每个子序列进行直接插入排序，从当前的记录i(保存在r[0]中)开始，依次扫描当前子序列之前的元素(每个元素的间隔为d，因此每次循环j都减少d)以确保插入何时的位置。
本文所涉及的排序算法源码可以在这里下载。
