## 問題描述 > 有一個帶頭結點的單鏈表對其排序，使之遞增有序。 ## 算法思想 > 因為是單鏈表的一次排序，[練習題12](http://blog.csdn.net/u013595419/article/details/50504852)中采用的是插入排序的算法，同樣類似，我們可以想到使用選擇排序算法完成排序。選擇排序一共分成兩個部分，即查找最小值和將最小值結點插入合適的位置兩個部分。具體算法如下： ## 算法描述 ~~~ //查找最小值 LNode* FindMin(LNode* head) { LNode *pre=head; LNode *premin=head; LNode *p=head->next; LNode *min=head->next; while(p){ if(p->data<min->data){ min=p; premin=pre; } pre=p; p=p->next; } return premin; } //將最小值插入合適位置 void SelctionSort(LNode *rear, LNode *premin) { LNode *min=premin->next; if(min==NULL){ return; } premin->next=min->next; min->next=rear->next; rear->next=min; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LNode* FindMin(LNode*); void SelctionSort(LNode*, LNode*); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; head=CreatList(head); Print(head); LNode *premin=NULL; LNode *r=head; while(r){ premin=FindMin(r); SelctionSort(r, premin); r=r->next; } Print(head); return 0; } //頭插法建立單鏈表 LinkList CreatList(LNode *head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //查找最小值 LNode* FindMin(LNode* head) { LNode *pre=head; LNode *premin=head; LNode *p=head->next; LNode *min=head->next; while(p){ if(p->data<min->data){ min=p; premin=pre; } pre=p; p=p->next; } return premin; } //選擇排序 void SelctionSort(LNode *rear, LNode *premin) { LNode *min=premin->next; if(min==NULL){ return; } premin->next=min->next; min->next=rear->next; rear->next=min; } //打印全部結點 void Print(LNode *head){ LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~ 注：選擇排序與插入排序中，插入排序是將結點徹底取下來進行插入排序（即已造成斷鏈），而選擇排序中從頭至尾都沒有斷鏈，中途只是暫時取下結點，然后及時插入到合適位置。