1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct LinkNode{
  5     int val;
  6     struct LinkNode* next;
  7 }LinkNode;
  8 
  9 LinkNode* CreateList(int A[], int count)
 10 {
 11     LinkNode* head = (LinkNode*)malloc(sizeof(LinkNode));
 12     head->val = A[0];
 13     head->next = NULL;
 14 
 15     LinkNode* p = head;
 16     
 17     for (int i = 1; i < count; ++i)
 18     {
 19         p->next = (LinkNode*)malloc(sizeof(LinkNode));
 20         p->next->val = A[i];
 21         p->next->next = NULL;
 22         p = p->next;
 23     }
 24 
 25     return head;
 26 }
 27 
 28 //asscending sort link list 
 29 //
 30 LinkNode* SortLinkListBubble(LinkNode* head)
 31 {
 32     if (NULL == head)
 33     {
 34         return head;
 35     }
 36 
 37     //points to the last, also the bigest value node
 38     LinkNode* lastN = NULL;
 39 
 40     while(true)
 41     {
 42         LinkNode* n = head->next;
 43 
 44         if (n == lastN)
 45         {
 46             break;
 47         }
 48 
 49         if (n->val < head->val)
 50         {
 51             head->next = n->next;
 52             n->next = head;
 53             head = n;
 54         }
 55 
 56         LinkNode* pre = head;
 57         LinkNode* cur = head->next;
 58         LinkNode* tmp;
 59         n = cur->next;
 60 
 61         while(lastN != n)
 62         {
 63             if (n->val < cur->val)
 64             {
 65                 tmp = n->next;
 66                 cur->next = n->next;
 67                 n->next = cur;
 68                 pre->next = n;
 69                 n = tmp;
 70             }
 71             else
 72             {
 73                 n = n->next;
 74             }
 75             pre = pre->next;
 76             cur = cur->next;
 77         }
 78 
 79         lastN = cur;
 80     }
 81 
 82     return head;
 83 }
 84 
 85 LinkNode* SortLinkListInsertion(LinkNode* head)
 86 {
 87     if (NULL == head || NULL == head->next)
 88     {
 89         return head;
 90     }
 91 
 92     LinkNode* r = head->next;
 93     LinkNode* tmp;
 94     head->next = NULL;
 95 
 96     while(NULL != r)
 97     {
 98         if (r->val < head->val)
 99         {
100             tmp = r->next;
101             r->next = head;
102             head = r;
103             r = tmp;
104         }
105         else
106         {
107             LinkNode* p = head;
108             while(NULL != p->next)
109             {
110                 if (r->val >= p->val && r->val <= p->next->val)
111                 {
112                     tmp = r->next;
113                     r->next = p->next;
114                     p->next = r;
115                     r = tmp;
116                     break;
117                 }
118                 else
119                 {
120                     p = p->next;
121                 }
122             }
123 
124             if (NULL == p->next)
125             {
126                 tmp = r->next;
127                 r->next = NULL;
128                 p->next = r;
129                 r = tmp;
130             }
131         }
132     }
133 
134     return head;
135 }
136 
137 LinkNode* SortLinkListSelection(LinkNode* head)
138 {
139     if (NULL == head || NULL == head->next)
140     {
141         return head;
142     }
143 
144     LinkNode* p = NULL;
145     LinkNode* pre = NULL;
146     LinkNode* pmin = NULL;
147     LinkNode* pminpre = NULL;
148     LinkNode* L = NULL;
149     LinkNode* Ltail = NULL;
150 
151     while (NULL != head && NULL != head->next)
152     {
153         pminpre = pmin = head;
154         
155         if (head->val > head->next->val)
156         {
157             pmin = head->next;
158         }
159 
160         pre = head;
161         p = head->next;
162 
163         while(NULL != p)
164         {
165             if (pmin->val > p->val)
166             {
167                 pminpre = pre;
168                 pmin = p;
169             }
170             pre = pre->next;
171             p = p->next;
172         }
173 
174         //delete pmin from original list
175         if (pmin == head)
176         {
177             head = head->next;
178         }
179         else
180         {
181             pminpre->next = pmin->next;
182         }
183 
184         //add it to the new list
185         if (NULL == L)
186         {
187             L = Ltail = pmin;
188             pmin->next = NULL;
189         }
190         else{
191             Ltail->next = pmin;
192             Ltail = pmin;
193             pmin->next = NULL;
194         }
195     }
196 
197     //do not forget the last node
198 
199     Ltail->next = head;
200     return L;
201 }
202 
203 void ShowList(LinkNode* L)
204 {
205     LinkNode* p = L;
206     printf("%d", p->val);
207 
208     while(p->next)
209     {
210         p = p->next;
211         printf("-->%d", p->val);
212     }
213 
214     printf("\n");
215 }
216 
217 int main(int argc, char *argv[])
218 {
219     //int A[] = {3, 6, 9, 8, 5, 2, 1, 4, 7, 0};
220     int A[] = {3, 6, 9, 8, 3, 2, 1, 2, 7, 6};
221     
222     LinkNode* L = CreateList(A, 10);
223 
224     ShowList(L);
225 
226     //L = SortLinkListInsertion(L);
227 
228     //L = SortLinkListBubble(L);
229 
230     L = SortLinkListSelection(L);
231 
232     ShowList(L);
233 
234     return 0;
235 }