链表的选择排序

具体分析： 引进一个v

NODE *v=(NODE*)malloc(sixeof(NODE));

V u h

45 65 54 80 90 30 p p1 p2 p3 p4 p5 p6 v->next =h; h=v; 把v插入h和p1(45)之间 先比较p1==u(45)和p2 (65)

为了适合循环： v->next->score， u->next->score表示要比较的数据：u->score==45，p2.score == 65

P=v; u=v->next ; （v->next==u） u->score==45 , v->next->score==45

p2==u->next==65

p2.score= u->next->score==65 for(p=v,u=v->next; u->next!=NILL; u=u->next) if( p->next->score < u->next->score) p=u; 找出最大的表u->next->score==(90)， 然后交换(90) (45) v u u u (即max）

45 65 54 80 90 30 p 把30 接到80后面： 90 的指针要保存

45接到90后面 90替代45位置

一、90要独立出来，同时30 接到80后面，需要两个指针： 1. p=u?, u=p->next : p指向 80 u指向 90 90要独立出来，所以要用指针u指向它，以免丢掉， u要移走，所以先用p指向 80

2. p->next =u->next : 30 接到80后面 二、 : 45接到90后面， u->next=v->next; 三、90替代45位置 v->next =u :

V=v->next, u=v-.next 准备下一轮

NODE *bubblesort(NODE *h) {NODE *v,*u,*p;

v = (NODE *)malloc(sizeof(NODE)); v->next =h; h=v;

while (v->next != NULL) //选择法

{ for(p = v, u = v->next; u->next != NULL; u = u->next) if (u->next->score > p->next->score ) p = u; //找到最大的

//u已移动，但队列未动

if (p != v) { u = p->next; p->next = u->next; //ok

u->next =v->next; v->next =u; } v=v->next;

} return h->next; //h; }

******************************* 14．Sort()排序

由于学生信息采用的是单链表存储结构，所以选用直接插入算法较为简单。

直接插入算法的基本方法是：每步将一个待排序的记录按其排序码值的大小插到前面已经排好序的表中，直到全部插入为止。 基于这样的方法首先将链表的头结点看作是已排好序的结点，然后取下一个结点作为待排序的结点，插入到已排好序的表中。由于单链表的特性，所以具体的思路如下：

(1)先将原表头结点作为新排好序表的头结点h，原表下一个结点作为原表头结点h1。设原表如图1l— 所示，表中只列出总分数据。

图 ．11设新表头结点 即 h是新链表， h1是旧链表

(2)原表头结点为待排序结点，

将其总分与新表结点的总分进行比较，如果待排序结点总分大，则插在新表的头，否则插入在其后，原表头结点后移一位，如图 ．12所示。

(3)重复第二步，即将原表头结点的总分和新表结点的总分进行比较，如果待排序结点总分小，则移动新表指针，直到找到合适的位置将其插入，直到原表为空，所有结点排序完毕，如图 ．13所示。

这个排序算法实际上是先从原表删除头结点，

然后在新表中查找到合适的位置，进行插入。待排序结点的插入