==========================
 功能：選擇排序(由小到大)
 返回：指向鏈表表頭的指針
==========================
*/

/*
 選擇排序的基本思想就是反復(fù)從還未排好序的那些節(jié)點中，
 選出鍵值（就是用它排序的字段，我們?nèi)W(xué)號num為鍵值）最小的節(jié) 點，
 依次重新組合成一個鏈表。

 我認(rèn)為寫鏈表這類程序，關(guān)鍵是理解：
 head存儲的是第一個節(jié)點的地址，head->next存儲的是第二個節(jié)點的地址；
 任 意一個節(jié)點p的地址，只能通過它前一個節(jié)點的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個節(jié)點的鏈表選擇排序

1、先在原鏈表中找最小的，找到一個后就把它放到另一個空的鏈表中；
2、空鏈表中安放第一個進來的節(jié)點，產(chǎn)生一個有序鏈表,并且讓它在原鏈 表中分離出來（此時要注意原鏈表中出來的是第一個節(jié)點還是中間其它節(jié)點）；
3、繼續(xù)在原鏈表中找下一個最小的，找到后把它放入有序鏈表的尾指針的 next,然后它變成其尾指針；
*/
struct student *SelectSort(struct student *head)
{
 struct student *first; /*排列后有序鏈的表頭指針*/
 struct student *tail; /*排列后有序鏈的表尾指針*/
 struct student *p_min; /*保留鍵值更小的節(jié)點的前驅(qū)節(jié)點的指針*/
 struct student *min; /*存儲最小節(jié)點*/
 struct student *p; /*當(dāng)前比較的節(jié)點*/
 
 first = NULL;
 while (head != NULL) /*在鏈表中找鍵值最小的節(jié)點。*/
 {
  /*注意：這里for語句就是體現(xiàn)選擇排序思想的地方*/
  for (p=head,min=head; p->next!=NULL; p=p->next) /*循環(huán)遍歷鏈表中的節(jié)點，找出此時最小的節(jié)點。*/
  {  
   if (p->next->num < min->num) /*找到一個比當(dāng)前min小的節(jié)點。*/
   {
    p_min = p; /*保存找到節(jié)點的前驅(qū)節(jié)點：顯然p->next的前驅(qū)節(jié)點是p。*/
    min = p->next; /*保存鍵值更小的節(jié)點。*/
   }
  }
 
  /*上面for語句結(jié)束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應(yīng)的條件判斷，安排它離開原來的鏈表。*/
 
  /*第一件事*/
  if (first == NULL) /*如果有序鏈表目前還是一個空鏈表*/
  {
   first = min; /*第一次找到鍵值最小的節(jié)點。*/
   tail = min; /*注意：尾指針讓它指向最后的一個節(jié)點。*/
  }
  else /*有序鏈表中已經(jīng)有節(jié)點*/
  {
   tail->next = min; /*把剛找到的最小節(jié)點放到最后，即讓尾指針的next指向它。*/
   tail = min; /*尾指針也要指向它。*/
  } 

  /*第二件事*/
  if (min == head) /*如果找到的最小節(jié)點就是第一個節(jié)點*/
  {
   head = head->next; /*顯然讓head指向原h(huán)ead->next,即第二個節(jié)點，就OK*/
  }
  else /*如果不是第一個節(jié)點*/
  {
   p_min->next = min->next; /*前次最小節(jié)點的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表。*/
  } 
 }

 if (first != NULL) /*循環(huán)結(jié)束得到有序鏈表first*/
 {
  tail->next = NULL; /*單向鏈表的最后一個節(jié)點的next應(yīng)該指向NULL*/
 }
 head = first;
 return head;
}

/*
==========================
 功能：直接插入排序(由小到大)
 返回：指向鏈表表 頭的指針
==========================
*/

/*
 直接插入排序的基本思想就是假設(shè)鏈表的前面n-1個節(jié)點是已經(jīng)按鍵值
 （就是用它排序的字段，我們?nèi)W(xué)號num為鍵值）排好 序的，對于節(jié)點n在
 這個序列中找插入位置，使得n插入后新序列仍然有序。按照這種思想，依次
 對鏈表從頭到尾執(zhí)行一遍，就可以使無序鏈 表變?yōu)橛行蜴湵怼?
 
單向鏈表的直接插入排序圖示：
---->[1]---->[3]----> [2]...---->[n]---->[NULL]（原鏈表）
head   1->next  3->next  2->next   n->next

---->[1]---->[NULL]（從原鏈表中取第1個節(jié)點作為只有一個節(jié)點的有序鏈表）
head
圖11

---->[3]---->[2]...---->[n]---->[NULL]（原鏈表剩下用于直接插入排序的節(jié)點）
first   3->next  2->next   n->next
圖12

---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后鏈表）
head   1->next  2->next  3->next   n->next

圖13：有N個節(jié)點的鏈表直接插入排序

1、先在原鏈表中以第一個節(jié)點為一個有序鏈表，其余節(jié)點為待定節(jié)點。
2、從圖12鏈表中取節(jié)點，到圖11鏈表中定位插入。
3、上面 圖示雖說畫了兩條鏈表，其實只有一條鏈表。在排序中，實質(zhì)只增加了一個用于指向剩下需要排序節(jié)點的頭指針first罷了。
   這一點請讀者務(wù)必搞清楚，要不然就可能認(rèn)為它和上面的選擇排序法一樣了。
*/
struct student *InsertSort(struct student *head)
{
 struct student *first; /*為原鏈表剩下用于直接插入排序的節(jié)點頭指針*/
 struct student *t; /*臨時指針變量：插入節(jié)點*/
 struct student *p; /*臨時指針變量*/
 struct student *q; /*臨時指針變量*/
 
 first = head->next; /*原鏈表剩下用于直接插入排序的節(jié)點鏈表：可根據(jù)圖12來理解。*/
 head->next = NULL; /*只含有一個節(jié)點的鏈表的有序鏈表：可根據(jù)圖11來理解。*/

 while (first != NULL) /*遍歷剩下無序的鏈表*/
 {
  /*注意：這里for語句就是體現(xiàn)直接插入排序思想的地方*/
  for (t=first, q=head; ((q!=NULL) && (q->num < t->num)); p=q, q=q->next); /*無序節(jié)點在有序鏈表中找插入的位置*/
 
  /*退出for循環(huán)，就是找到了插入的位置*/
  /*注意：按道理來說，這句話可以放到下面注釋了的那個位置也應(yīng)該對的，但是就是不能。原因：你若理解了上面的第3條，就知道了。*/
  first = first->next; /*無序鏈表中的節(jié)點離開，以便它插入到有序鏈表中。*/
 
  if (q == head) /*插在第一個節(jié)點之前*/
  {
   head = t;   
  }
  else /*p是q的前驅(qū)*/
  {
   p->next = t;  
  }
  t->next = q; /*完成插入動作*/
  /*first = first->next;*/
 }
 return head;
}

/*
==========================
 功能：冒泡排序(由小到大)
 返回：指向鏈表表頭的 指針
==========================
*/

/*
 直接插入排序的基本思想就是對當(dāng)前還未排好序的范圍內(nèi)的全部節(jié)點，
 自上而下對相鄰的兩個節(jié)點依次進行比較和調(diào)整，讓鍵值 （就是用它排
 序的字段，我們?nèi)W(xué)號num為鍵值）較大的節(jié)點往下沉，鍵值較小的往
 上冒。即：每當(dāng)兩相鄰的節(jié)點比較后發(fā)現(xiàn)它們的排序與 排序要求相反時，
 就將它們互換。

單向鏈表的冒泡排序圖示：
---->[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個節(jié)點的鏈表冒泡排序

任意兩個相鄰節(jié)點p、q位置互換圖示:
假設(shè)p1->next指向p，那么顯然p1->next->next就指向q,
p1->next->next->next 就指向q的后繼節(jié)點，我們用p2保存
p1->next->next指針。即：p2=p1->next->next，則 有：
[  ]---->[p]---------->[q]---->[  ]（排序前）
  p1->next  p1->next->next  p2->next
圖15

[  ]---->[q]---------->[p]---->[  ]（排序后）

圖16

1、排序后q節(jié)點指向p節(jié)點，在調(diào)整指向之前，我們要保存原p的指向節(jié)點地址，即：p2=p1->next->next；
2、 順著這一步一步往下推,排序后圖16中p1->next->next要指的是p2->next,所以 p1->next->next=p2->next;
3、在圖15中p2->next原是q發(fā)出來的指向，排序后圖16中 q的指向要變?yōu)橹赶騪的，而原來p1->next是指向p的，所以p2->next=p1->next;
4、在圖15中 p1->next原是指向p的，排序后圖16中p1->next要指向q,原來p1->next->next（即p2)是指向q 的，所以p1->next=p2;
5、至此，我們完成了相鄰兩節(jié)點的順序交換。
6、下面的程序描述改進了一點就是記錄了每次最后一 次節(jié)點下沉的位置，這樣我們不必每次都從頭到尾的掃描，只需要掃描到記錄點為止。
   因為后面的都已經(jīng)是排好序的了。
*/
struct student *BubbleSort(struct student *head)
{
 struct student *endpt; /*控制循環(huán)比較*/
 struct student *p; /*臨時指針變量*/
 struct student *p1;
 struct student *p2;

 p1 = (struct student *)malloc(LEN);
 p1->next = head; /*注意理解：我們增加一個節(jié)點，放在第一個節(jié)點的前面，主要是為了便于比較。因為第一個節(jié)點沒有前驅(qū)，我們不能交換地址。*/
 head = p1; /*讓head指向p1節(jié)點，排序完成后，我們再把p1節(jié)點釋放掉*/

 for (endpt=NULL; endpt!=head; endpt=p) /*結(jié)合第6點理解*/
 {
  for (p=p1=head; p1->next->next!=endpt; p1=p1->next)
  {
   if (p1->next->num > p1->next->next->num) /*如果前面的節(jié)點鍵值比后面節(jié)點的鍵值大，則交換*/
   {
    p2 = p1->next->next; /*結(jié)合第1點理解*/
    p1->next->next = p2->next; /*結(jié)合第2點理解*/
    p2->next = p1->next; /*結(jié)合第3點理解*/
    p1->next = p2; /*結(jié)合第4點理解*/
    p = p1->next->next; /*結(jié)合第6點理解*/
   }
  }
 }

 p1 = head; /*把p1的信息去掉*/
 head = head->next; /*讓head指向排序后的第一個節(jié)點*/
 free(p1); /*釋放p1*/
 p1 = NULL; /*p1置為NULL，保證不產(chǎn)生“野指針”，即地址不確定的指針變量*/

 return head;
}

/*
==========================
 功能：插入有序鏈表的某個節(jié)點的后面(從小到大)
 返 回：指向鏈表表頭的指針
==========================
*/

/*
有序鏈表插入節(jié)點示意圖：

---->[NULL]（空有序鏈表）
head

圖18：空有序鏈表（空有序鏈表好解決，直接讓head指向它就是了。）

以下討論不為空的有序鏈表。
---->[1]---->[2]---->[3]...----> [n]---->[NULL]（有序鏈表）
head   1->next  2->next  3->next   n->next

圖18：有N個節(jié)點的有序鏈表

插入node節(jié)點的位置有兩種情況：一是第一個節(jié)點前，二是其它節(jié)點前或后。

---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL]
head  node->next  1->next  2->next  3->next   n->next

圖19：node節(jié)點插在第一個節(jié)點前

---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
head   1->next  2->next  3->next    node->next  n->next

圖20：node節(jié)點插在其它節(jié)點后
*/
struct student *SortInsert(struct student *head, struct student *node)
{
 struct student *p; /*p保存當(dāng)前需要檢查的節(jié)點的地址*/
 struct student *t; /*臨時指針變量*/

 if (head == NULL) /*處理空的有序鏈表*/
 {
  head = node;
  node->next = NULL;
  n += 1; /*插入完畢，節(jié)點總數(shù)加1*/
  return head;
 }

 p = head; /*有序鏈表不為空*/
 while (p->num < node->num && p != NULL) /*p指向的節(jié)點的學(xué)號比插入節(jié)點的學(xué)號小，并且它不等于NULL*/
 {
  t = p; /*保存當(dāng)前節(jié)點的前驅(qū)，以便后面判斷后處理*/
  p = p->next; /*后移一個節(jié)點*/
 }
 
 
 if (p == head)  /*剛好插入第一個節(jié)點之前*/
 {
  node->next = p;
  head = node;    
 }
 else /*插入其它節(jié)點之后*/
 { 
  t->next = node; /*把node節(jié)點加進去*/
  node->next = p; 
 }
 n += 1; /*插入完畢，節(jié)點總數(shù)加1*/
 
 return head;
}

/*

測試代碼如下：

*/

/*測試SelectSort():請編譯時去掉注釋塊*/

 /*
 head = SelectSort(head);
 Print(head);
 */
 
 /*測 試InsertSort():請編譯時去掉注釋塊*/

 /*
 head = InsertSort(head);
 Print(head);
 */

 /*測試BubbleSort():請編譯時去掉注釋塊*/

 /*
 head = BubbleSort(head);
 Print(head);
 */

 /*測試SortInsert():上面創(chuàng)建鏈表，輸入節(jié)點時請注意學(xué)號num從小到大的順序。請編譯時去掉注釋塊*/

 /*
 stu = (struct student *)malloc(LEN);
 printf("\nPlease input insert node -- num,score: ");
 scanf("%ld,%f",&stu->num,&stu->score);
 head = SortInsert(head,stu);
 free(stu);
 stu = NULL;
 Print(head);
 */