|
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
head 1->next 2->next 3->next n->next
图13：有N个节点的链表直接插入排序
1、先在原链表中以第一个节点为一个有序链表，别的节点为待定节点。
2、从图12链表中取节点，到图11链表中定位插入。
3、上面图示虽说画了两条链表，着实只有一条链表。在排序中，实质只增进了一个用于指向剩下必要排序节点的头指针first而已。
这一点请读者务必搞清晰，要否则就也许以为它和上面的选择排序法一样了。
对链表举办直接插入排序的函数为：
/*
==========================
成果：直接插入排序(由小到大)
返回：指向链表表头的指针
==========================
*/
struct student *InsertSort (struct student *head)
{
struct student *first; //为原链表剩下用于直接插入排序的节颔首指针
struct student *t; //姑且指针变量：插入节点
struct student *p,*q; //姑且指针变量
first = head->next; //原链表剩下用于直接插入排序的节点链表：可按照图12来领略
head->next = NULL; //只含有一个节点的链表的有序链表：可按照图11来领略
while(first != NULL) //遍历剩下无序的链表
{
//留意：这里for语句就是浮现直接插入排序头脑的处所
for (t = first,q = head; ((q != NULL) && (q->num < t->num)); p = q,q = q->next); //无序节点在有序链表中找插入的位置
//退出for轮回，就是找到了插入的位置，应该将t节点插入到p节点之后，q节点之前
//留意：按原理来说，这句话可以放到下面注释了的谁人位置也应该对的，可是就是不能。缘故起因：你若领略了上面的第3条，就知道了
//下面的插入就是将t节点等于first节点插入到p节点之后，已经改变了first节点，以是first节点应该在被修改之前去后移动，不能放到下面注释的位置上去
first = first->next; //无序链表中的节点分开，以便它插入到有序链表中
if (q == head) //插在第一个节点之前
{
head = t;
}
else //p是q的前驱
{
p->next = t;
}
t->next = q; //完成插入举措
//first = first->next;
}
return head;
}
对链表举办冒泡排序的根基头脑就是对当前还未排好序的范畴内的所有节点，自上而下对相邻的两个节点依次举办较量和调解，让键值（就是用它排 序的字段，我们取学号num为键值）较大的节点往下沉，键值较小的往上冒。即：每当两相邻的节点较量后发明它们的排序与排序要求相反时，就将它们交流。
单向链表的冒泡排序图示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）
head 1->next 3->next 2->next n->next
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
head 1->next 2->next 3->next n->next
图14：有N个节点的链表冒泡排序
恣意两个相邻节点p、q位置交流图示:
假设p1->next指向p，那么显然p1->next->next就指向q,
p1->next->next->next就指向q的后继节点，我们用p2生涯
p1->next->next指针。即：p2=p1->next->next，则有：
[ ]---->[p]---------->[q]---->[ ]（排序前）
p1->next p1->next->next p2->next
图15
[ ]---->[q]---------->[p]---->[ ]（排序后）
图16 （编辑：湖南网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
