前面章节中所介绍到的三种插入排序算法,其基本结构都采用数组的形式进行存储,因而无法避免排序过程中产生的数据移动的问题。如果想要从根本上解决只能改变数据的存储结构,改用链表存储。
表插入排序,即使用链表的存储结构对数据进行插入排序。在对记录按照其关键字进行排序的过程中,不需要移动记录的存储位置,只需要更改结点间指针的指向。
链表的存储结构用代码表示为:
#define SIZE 100
typedef struct {
int rc;//记录项
int next;//指针项,由于在数组中,所以只需要记录下一个结点所在数组位置的下标即可。
}SLNode;
typedef struct {
SLNode r[SIZE];//存储记录的链表
int length;//记录当前链表长度
}SLinkListType;
在使用数组结构表示的链表中,设定数组下标为 0 的结点作为链表的表头结点,并令其关键字取最大整数。则表插入排序的具体实现过程是:首先将链表中数组下标为 1 的结点和表头结点构成一个循环链表,然后将后序的所有结点按照其存储的关键字的大小,依次插入到循环链表中。
例如,将无序表{49,38,76,13,27}用表插入排序的方式进行排序,其过程为:
从表插入排序的实现过程上分析,与直接插入排序相比只是避免了移动记录的过程(修改各记录结点中的指针域即可),而插入过程中同其它关键字的比较次数并没有改变,所以表插入排序算法的时间复杂度仍是O(n2)。
在表插入排序算法求得的有序表是用链表表示的,也就注定其只能进行顺序查找。而如果想用折半查找的算法,就需要对链表进行再加工,即对链表中的记录进行重新排列,具体做法为:遍历链表,将链表中第 i 个结点移动至数组的第 i 个下标位置中。
例如,上表是已经构建好的链表,对其进行再加工的过程为:
重新排列的具体代码实现为:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
typedef struct {
int rc;//记录项
int next;//指针项,由于在数组中,所以只需要记录下一个结点所在数组位置的下标即可。
}SLNode;
typedef struct {
SLNode r[SIZE];//存储记录的链表
int length;//记录当前链表长度
}SLinkListType;
//重新排列函数
void Arrange(SLinkListType *SL){
//令 p 指向当前要排列的记录
int p=SL->r[0].next;
for (int i=1; i<SL->length; i++) {
//如果条件成立,证明原来的数据已经移动,需要通过不断找 next 域,找到其真正的位置
while (p<i) {
p=SL->r[p].next;
}
//找到之后,令 q 指针指向其链表的下一个记录所在的位置
int q=SL->r[p].next;
//条件成立,证明需要同下标为 i 的记录进行位置交换
if (p!=i) {
SLNode t;
t=SL->r[p];
SL->r[p]=SL->r[i];
SL->r[i]=t;
//交换完成后,该变 next 的值,便于后期遍历
SL->r[i].next=p;
}
//最后令 p 指向下一条记录
p=q;
}
}
int main(int argc, const char * argv[]) {
SLinkListType *SL=(SLinkListType*)malloc(sizeof(SLinkListType));
SL->length=6;
SL->r[0].rc=0;
SL->r[0].next=4;
SL->r[1].rc=49;
SL->r[1].next=3;
SL->r[2].rc=38;
SL->r[2].next=1;
SL->r[3].rc=76;
SL->r[3].next=0;
SL->r[4].rc=13;
SL->r[4].next=5;
SL->r[5].rc=27;
SL->r[5].next=2;
Arrange(SL);
for (int i=1; i<6; i++) {
printf("%d ",SL->r[i].rc);
}
return 0;
}
运行结果为: