插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到已排好序的子序列中的适当位置，直到全部记录插入完成为止。本文将介绍两种常见的插入排序方法：直接插入排序和希尔排序。

直接插入排序(Straight Insertion Sorting)

　　基本思想: 将待排序的无序数列S[n]看成是一个仅含有一个元素的有序数列S[0]和一个无序数列S[1,…,n-1]，将无序数列中的元素依次插入到有序数列中，从而获得最终的有序数列【动画模拟演示】。

　　算法流程:
　　1. 初始时，S[0]自成一个有序区，无序区为S[1,…,n-1]，令i=1；
　　2. 将S[i]并入当前的有序区S[0,…i-1]；
　　3. i++并重复步骤2，直到i=n-1，排序完成。
　　示意图: 初始无序数列为49，38，65，97，76，13，27，49

　　说明: 排序过程的某一中间时刻，S被划分成两个子区间S[0,…,i-1](已排好序的有序区)和S[i,…,n-1](当前未排序的无序区)。直接插入排序与打扑克牌时整理手上的牌非常类似，摸来的第一张牌无需整理，此后每次从桌上的牌(无序区)中摸最上面的一张并插入手牌(有序区)中正确的位置上，为了找到这个正确的位置，须自左向右(自右向左、折半等查找方法)将摸来的牌与手牌逐一比较。如果碰见一个和插入元素相等的，那么把待插入元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，所以插入排序是稳定的。
　　哨兵: 有时候引进附加记录S[0]作为哨兵，待排序数列变成S[1,…n]。实际上，一切为简化边界条件而引入的附加节点(元素)均可称为哨兵。单链表中的头节点实际上就是一个哨兵。哨兵有两个作用：保存待插入元素S[i]，从而不至于因记录后移而丢失S[i]；防止下标越界，因为S[i]等于S[0]，比较到S[0]时循环就会结束，从而避免了在循环内的每一次检测下标是否越界。引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间，所以不能把哨兵视为雕虫小技。
　　C++实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//直接插入排序，版本1
void StraightInsertionSort1(int a[], int n)
{
    int i, j, k;
    for(i=1; i<n; i++)
    {
        //找到要插入的位置
        for(j=0; j<i; j++)
            if(a[j]>a[i])
                break;
        //插入并后移剩余元素
        if(j != i)
        {
            int temp = a[i];
            for(k=i-1; k>=j; k--)
                a[k+1] = a[k];
            a[j] = temp
        }
    }
}
//直接插入排序，版本2:搜索和后移同时进行
void StraightInsertionSort2(int a[], int n)
{
    int i, j, k;
    for(i=1; i<n; i++)
        if(a[i]<a[i-1])
        {
            int temp = a[i];
            for(j=i-1; j>=0 && a[j]>temp; j--)
                a[j+1] = a[j];
            a[j+1] = temp;
        }
}
//直接插入排序，版本3:用数据交换代替数据后移
void StraightInsertionSort3(int a[], int n)
{
    for(int i=1; i<n; i++)
        for(int j=i-1; j>=0 && a[j]>a[j+1]; j--)
            Swap(a[j],a[j+1]);
}

　　算法复杂度: 采用直接插入排序对n个元素排序存在最好情况和最坏情况。最好情况就是序列已经是有序的了，在这种情况下需要进行的比较次数是\(n-1\)。最坏情况就是序列是反序的，那么此时需要进行的比较次数是\(\frac{1}{2} n(n-1)\)。平均来说直接插入排序算法时间复杂度为\(O(n^2)\)。因而，直接插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如量级小于千，那么直接插入排序还是一个不错的选择。在STL的sort算法和stdlib的qsort算法中，都将直接插入排序作为快速排序的补充，用于少量元素的排序(通常为8个或以下)。直接插入排序是一个就地(in-place)排序，所需的空间为\(O(1)\)。
　　直接插入排序的优化：在查找待插入位置时通过折半查找减少关键字的比较次数；用静态链表存储待排序序列可以减少移动次数。

希尔排序(Shell Sort)

　　基本思想: 希尔排序