单链表线性表的插入排序算法

巧若拙

最近看《啊哈，算法》，写了一个对单链表线性表进行插入排序的算法，其中用到一个小技巧，不用定位插入位置的前驱结点，自我感觉很巧妙，大家评评看。
typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等


typedef struct Node{
ElemType data;//数据域
struct Node *next;//指针域
} Node;


typedef struct Node *LinkList;


/*
函数功能：给单链表线性表排序
初始条件：单链表线性表L已经存在，该线性表带一个不存储信息的头结点；
操作结果：使用插入排序的方法，为单链表线性表排序。
操作成功返回OK，否则返回ERROR
*/
Status ListSort(LinkList *L)
{
ElemType temp;
LinkList q, p, pos = (*L)->next; //p指向第1个结点

if (!pos)
{
printf("空表!");
return ERROR;
}
while (pos->next != NULL)//寻找最后一个结点
{
pos = pos->next;
}

while ((*L)->next != pos)
{
q = (*L)->next;
(*L)->next = q->next;
p = pos;
while (p->next != NULL && p->data < q->data) //寻找插入点
{
p = p->next;
}

q->next = p->next; //在p后插入q
p->next = q;

if (p->data > q->data) //若p的值大于q，交换二者的值，以保证线性表有序
{
temp = p->data;
p->data = q->data;
q->data = temp;
}

}

return OK;
}

rosynirvana

你自己试验过这段代码吗？

while (pos->next != NULL)//寻找最后一个结点
{
pos = pos->next;
}
……
p = pos;
while (p->next != NULL && p->data < q->data)

pos指向链表最后一个节点，p=pos，然后还要验证p->next != NULL ?

如果如你所说“不用定位插入位置的前驱结点”，但是你用了(*L), pos, p, q，4个指针，也没有什么优势

巧若拙

测试过的。
pos在排序开始的时候是指向最后一个结点的，但后来随着不断插入新结点，pos就不是指向最后一个结点了，而是指向有序链表的第一个结点，即pos及其后面的结点是有序的。

巧若拙

算法的巧妙之处在于即使结点数据比pos->data大，也是在pos后面插入，通过交换数据值来确保链表有序。
否则要遍历链表去寻找pos的前驱结点，时间复杂度变大了。