学步园

      若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序。存储结构定义如下：

#define SIZE 100        //静态链表容量
typedef struct  
{
string rc;        //记录项
    int next;        //指针项
}SLNode;                //表结点类型
typedef struct
{
    SLNode r[SIZE];    //0号单元为表头结点
    int length;        //链表当前长度
}SLinkListType;        //静态链表类型

      为了方便插入，设数组中下标为“0”的分量为表头结点，并令表头结点记录的关键字取最大整数MAXINT。则表插入排序的过程描述如下：首先将静态链表中数组下标为“1”的分量（结点）和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量（结点）按记录关键字非递减有序插入到循环链表中。时间复杂度为O(n^2)。理解：和直接插入排序同样的处理方式，只不过不需要移动记录，只要改变next域。表插入排序的结果只是求得一个有序链表，所以只能进行顺序查找。

算法同直接插入排序。