C语言结构体链表的排序方法汇总

==========================
 功能：选择排序(由小到大)
 返回：指向链表表头的指针
==========================
*/

/*
 选择排序的基本思想就是反复从还未排好序的那些节点中，
 选出键值（就是用它排序的字段，我们取学号num为键值）最小的节点，
 依次重新组合成一个链表。

 我认为写链表这类程序，关键是理解：
 head存储的是第一个节点的地址，head->next存储的是第二个节点的地址；
 任意一个节点p的地址，只能通过它前一个节点的next来求得。

单向链表的选择排序图示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）
head   1->next  3->next  2->next   n->next

---->[NULL]（空链表）
first
tail

---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
first   1->next  2->next  3->next   tail->next

图10：有N个节点的链表选择排序

1、先在原链表中找最小的，找到一个后就把它放到另一个空的链表中；
2、空链表中安放第一个进来的节点，产生一个有序链表,并且让它在原链表中分离出来（此时要注意原链表中出来的是第一个节点还是中间其它节点）；

3、继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针；
*/
struct student *SelectSort(struct student *head)
{
 struct student *first; /*排列后有序链的表头指针*/
 struct student *tail; /*排列后有序链的表尾指针*/ 
 struct student *p_min; /*保留键值更小的节点的前驱节点的指针*/
 struct student *min; /*存储最小节点*/ 
 struct student *p; /*当前比较的节点*/
 
 first = NULL;
 while (head != NULL) /*在链表中找键值最小的节点。*/
 {
  /*注意：这里for语句就是体现选择排序思想的地方*/
  for (p=head,min=head; p->next!=NULL; p=p->next) /*循环遍历链表中的节点，找出此时最小的节点。*/
  {   
   if (p->next->num < min->num) /*找到一个比当前min小的节点。*/
   {
    p_min = p; /*保存找到节点的前驱节点：显然p->next的前驱节点是p。*/
    min = p->next; /*保存键值更小的节点。*/
   } 
  }
  
  /*上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表。*/
  
  /*第一件事*/
  if (first == NULL) /*如果有序链表目前还是一个空链表*/
  {
   first = min; /*第一次找到键值最小的节点。*/
   tail = min; /*注意：尾指针让它指向最后的一个节点。*/