排序耗时的操作主要分为两种：查找比较、记录移位。
1.表插入排序
在查找比较基础上，尽量减少记录移位步数，可以令排序操作耗时降低，表插入排序正是为减少移位次数而出现的。
在数据结构上，数据是存储在静态数组(表)中，而每个数组除了数据关键字外还记录了表中下一个记录，按记录遍历的关键字则是排序的结果。
如：有如下需要排序的数据:
| 关键字 | 5 | 1 | 3 | 2 | 4 |
| 下一个记录的表中位置 | - | - | - | - | - |
排序后得到的表为
| 关键字 | 5 | 1 | 3 | 2 | 4 |
| 下一个记录的表中位置 | -1 | 3 | 4 | 2 | 0 |
这里还需要提到重排记录的方法：
由于重排过程中，需要移动记录的位置，所以"下一个记录的表中位置"则会产生变化，而又因为重排过程中表中不同数据只会被访问一次，所以可以利用失效的"下一个记录的表中位置"记录未被访问的数据且因重排被移位的新位置。
重排时，以i记录已经排好的记录数量，p记录要重拍的关键字，如果p<i，表示要重拍的关键字被移位了，所以再获取表中的"下一个记录的表中位置"即可。
#include <stdio.h>
#include <stdlib.h> typedef struct{
int data;
int next;
}node;
typedef struct{
node *list;
int head;
}table; int main(void){
node *s;
int cnt=0, k, cntmax=10, nexttemp, datatemp, kk;
int head, preindex;
int p,i;
table mytable; s = (node*)malloc(sizeof(node)*10);
while(1){
scanf("%d", &datatemp);
if(datatemp<0)
break;
(s+cnt)->data = datatemp;
cnt++;
if(cnt==cntmax){
s = (node*)realloc(s, cntmax+10);
cntmax += 10;
}
}
mytable.list = s; head = 0;
s->next = -1; //-1表示链表表尾结点
//表插入排序
for(k=1; k<cnt; k++){
kk=head;
while(kk!=-1){
if((s+kk)->data>(s+k)->data){
if(kk==head){
head = k;
(s+k)->next = kk;
}
else{
(s+preindex)->next = k;
(s+k)->next = kk;
}
break;
}
else{
preindex = kk;
kk = (s+kk)->next;
}
}
if(kk==-1){
(s+preindex)->next = k;
(s+k)->next = -1;
}
}
mytable.head = head; for(k=mytable.head; k!=-1; k=(mytable.list+k)->next){
printf("%d ", (mytable.list+k)->data);
}
printf("\n"); //记录重排-->这里是难点~~
for(i=0, p=head; i<cnt; i++){
//i位置结点与k位置结点交换
while(p<i) //----->注意这里哟，逐个找回来
p = (s+p)->next;
k = (s+p)->next; //保存指向的下一个需要重排的关键字位置 if(p!=i){
datatemp = (s+p)->data;
nexttemp = (s+p)->next;
(s+p)->data = (s+i)->data;
(s+p)->next = (s+i)->next;
(s+i)->data = datatemp;
(s+i)->next = p;
} p = k;
}
for(i=0; i<cnt; i++){
printf("%d ", (mytable.list+i)->data);
}
printf("\n"); system("pause");
return 0;
}
其他排序请见后篇