插入排序：表安插
插入排序：表插入
所谓插入排序之表排序，是利用静态链表的形式，分两步完成排序。
一，对一个有序的循环链表，插入一新的元素，修改每个节点的后继指针的指向，使顺着这个指针的指向，元素是有序的。在这个过程中，我们不移动或交换元素，只是修改指针的指向。
二，顺着指针的指向调整元素的位置，使其在链表中真正做到物理有序。
思路：
- 构建一新的结构体类型，使其封装了值域和指针域。并增加一节点，当做头节点，为循环终止创造条件，头节点值域存贮的值应不小于原序列中的最大值。
- 初始化静态链表：使第一个节点和头节点构成循环的链表。由于链表中只有一个元素，那当然是有序的。
- 把后续的节点依次插入到该循环链表中，调整各节点的指针指向，使其沿着指针方向是有序的。
关键代码：
const int MAX = 1000; //这里的最大值，应设置好
typedef struct rec //Record 静态链表的节点类型
{
int data;
int next; //静态链表的链域可以这样写，大家应该见过很多次
}Rec;
void InsertSort(int a[], int n) //表插入
{
Rec *rec = new Rec[n+1];
for (int i = 0; i < n; i++) //把数据赋给链表
{
rec[i + 1].data = a[i];
rec[i + 1].next = 0;
}
rec[0].data = MAX;
rec[0].next = 1; //头节点和第一个节点构成了循环链表
int p, q;
for (int i = 2; i < n + 1; i++)
{
q = 0;
p = rec[q].next; //p指向当前待比较的节点，q指向前一个
while (rec[i].data >= rec[p].data) // >= 保证了排序的稳定性
{
q = p;
p = rec[q].next;
}
rec[i].next = p;
rec[q].next = i;
}
p = rec[0].next;
int i=0;
while(p!=0) //顺着静态链表的指针指向，回写数据到原数组
{
a[i++]=rec[p].data;
p=rec[p].next;
}
delete[]rec; //释放空间
}
小结：
说它是插入排序，是因为，每次都是把一个新的数据插入到原本有序的序列中，并且是从序列的头部开始比较。
大家测试下，看是否有问题。
p.s 也可以把静态链表也调整成物理有序的，比较简单，大家先想下，后续补上。