首页 > > 程序设计 > C/C++ >

【模板小程序】链表排序（qsort/insert_sort/mer…

2018-06-17 22:06:18来源：未知阅读 ()

前言

本文章整理了链表排序的三种方法，分别是快速排序、插入排序、归并排序。为适应不同用途，先给出常用的int版本，再在此基础上抽象出类模板。

一、针对整数的版本（常用）

文中链表定义：

1 //definition for singly-linked list.
2 struct ListNode
3 {
4     int val;
5     ListNode* next;
6     ListNode(int x) : val(x), next(NULL) {}
7 };

链表相关操作：

 1 //链表结点构造
 2 ListNode*  create_list_node(int val)
 3 {
 4     ListNode* pNode = new ListNode(val);
 5     return pNode;
 6 }
 7 //链表结点连接
 8 void connect_list_node(ListNode* pCur, ListNode* pNext)
 9 {
10     pCur->next = pNext;
11 }
12 
13 //销毁单个节点(其实用这个更好，不会出现空悬指针)
14 void destory_Node(ListNode** ppNode)
15 {
16     if(*ppNode != NULL)
17         delete *ppNode;
18     *ppNode = NULL;
19 }
20 
21 //链表销毁(注意，除头节点外，其他节点均变成了空悬指针，不建议此用法)
22 void destory_list(ListNode** ppHead)
23 {
24     ListNode** cur = ppHead;
25     while(*cur != NULL)
26     {
27         ListNode* tmp = (*cur)->next;//保存下一个节点
28         delete *cur;
29         *cur = NULL;
30         *cur = tmp;
31     }
32 }
33 
34 //链表打印（不支持有环的链表；如果链表有环，需判断环入口等等另外处理）
35 void print_list(ListNode* pHead)
36 {
37     ListNode* cur = pHead;
38     while(cur != NULL)
39     {
40         cout<< cur->val <<" ";
41         cur = cur->next;
42     }
43     cout<<endl;
44 }

三种排序方法：

 1 //链表快速排序
 2 class List_qsort
 3 {
 4 private:
 5     //交换元素
 6     void list_swap(int& lhs,int& rhs)
 7     {
 8         int tmp = lhs;
 9         lhs = rhs;
10         rhs = tmp;
11     }
12     //划分，使左边小于头结点元素，右边大于等于头结点元素
13     ListNode* list_partion(ListNode* pBegin,ListNode* pEnd)
14     {
15         if(pBegin == pEnd || pBegin->next == NULL)
16             return pBegin;
17 
18         ListNode* pSlow=pBegin;
19         ListNode* pFast=pBegin;
20         int key=pBegin->val;
21         while(pFast != pEnd)
22         {
23 
24             if(pFast->val < key)
25             {
26                 pSlow = pSlow->next;
27                 list_swap(pSlow->val,pFast->val);
28             }
29             pFast = pFast->next;
30         }
31 
32         list_swap(pSlow->val,pBegin->val);
33 
34         return pSlow;
35     }
36     //排序辅助函数
37     void _list_qsort(ListNode* pBegin,ListNode* pEnd)
38     {
39         if(pBegin == pEnd || NULL == pBegin->next)
40             return;
41         ListNode* mid=list_partion(pBegin,pEnd);
42         _list_qsort(pBegin,mid);
43         _list_qsort(mid->next,pEnd);
44     }
45 public:    
46     //排序入口函数(版本1：传值)
47     void list_qsort(ListNode* pHead)
48     {
49         if(pHead == NULL || pHead->next ==NULL)
50             return ;
51         _list_qsort(pHead,NULL);
52 
53     }
54 
55     /*
56     //排序入口函数(版本2：传指针)
57     void list_qsort(ListNode** ppHead)
58     {
59         if(*ppHead == NULL || (*ppHead)->next ==NULL)
60             return;
61         _list_qsort(*ppHead,NULL);
62     }
63     */
64 
65     /*
66     //排序入口函数(版本3：传引用)
67     void list_qsort(ListNode*& pHead)
68     {
69         if(NULL == pHead  || NULL == pHead->next )
70             return;
71         _list_qsort(pHead,NULL);
72     }
73     */
74 };

  1 //链表插入排序
  2 class List_insertion_sort
  3 {
  4 
  5     //版本1：指针的指针
  6 private:
  7     //对于待插入的节点，选择合适的位置插入
  8     void _list_insert_sort(ListNode** ppNode, ListNode *pNode)
  9     {
 10         ListNode* prev = NULL;
 11         ListNode* cur = NULL;
 12 
 13         if(pNode->val < (*ppNode)->val)
 14         {
 15             pNode->next = *ppNode;
 16             (*ppNode) = pNode;
 17             return;
 18         }
 19 
 20         cur = *ppNode;
 21 
 22         while(cur != NULL)
 23         {
 24             if(pNode->val < cur->val)
 25                 break;
 26 
 27             prev = cur;
 28             cur = cur->next;
 29         }
 30 
 31         pNode->next = cur;//或pNode->next = prev->next
 32         prev->next =pNode;
 33         return;
 34     }
 35 public:
 36     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
 37     void list_insert_sort(ListNode** ppNode)
 38     {
 39         ListNode* prev = NULL;
 40         ListNode* cur = NULL;
 41 
 42         if(NULL == ppNode || NULL == *ppNode)
 43             return;
 44 
 45         cur = (*ppNode)->next;
 46         (*ppNode)->next = NULL;
 47 
 48         while(cur != NULL)
 49         {
 50             prev = cur;
 51             cur = cur->next;
 52             _list_insert_sort(ppNode,prev);
 53         }
 54     }
 55 
 56     /*
 57     //版本2：指针的引用
 58 private:
 59     //对于待插入的节点，选择合适的位置插入
 60     void _list_insert_sort(ListNode*& ppNode, ListNode *pNode)
 61     {
 62         ListNode* prev = NULL;
 63         ListNode* cur = NULL;
 64 
 65         if(pNode->val < ppNode->val)
 66         {
 67             pNode->next = ppNode;
 68             ppNode = pNode;
 69             return;
 70         }
 71 
 72         cur = ppNode;
 73 
 74         while(cur != NULL)
 75         {
 76             if(pNode->val < cur->val)
 77                 break;
 78 
 79             prev = cur;
 80             cur = cur->next;
 81         }
 82 
 83         pNode->next = cur;//或pNode->next = prev->next
 84         prev->next =pNode;
 85         return;
 86     }
 87 public:
 88     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
 89     void list_insert_sort(ListNode*& ppNode)
 90     {
 91         ListNode* prev = NULL;
 92         ListNode* cur = NULL;
 93 
 94         if(NULL == ppNode)
 95             return;
 96 
 97         cur = ppNode->next;
 98         ppNode->next = NULL;
 99 
100         while(cur != NULL)
101         {
102             prev = cur;
103             cur = cur->next;
104             _list_insert_sort(ppNode,prev);
105         }
106     }
107 */
108 
109 };

 1 //链表归并排序
 2 class List_merge_sort
 3 {
 4 private:
 5     //合并两端链表
 6     //因为可能在头结点之前插入数据，故为ListNode** list1
 7     ListNode* list_merge(ListNode* list1, ListNode* list2)
 8     {
 9         if(NULL == list1)
10             return list2;
11         else if(NULL == list2)
12             return list1;
13 
14         ListNode* dummy = new ListNode(-1);//辅助头结点
15         dummy->next = list1;
16         ListNode* list1_cur = dummy;
17         ListNode* list2_cur = list2;
18 
19         while(list1_cur->next != NULL && list2_cur != NULL)
20         {
21             //cout<< list1_cur->next->val <<"==="<< list2_cur->val<<endl;
22             //把后面一段list2更小的元素插入前面一段list1中
23             if(list1_cur->next->val > list2_cur->val)//注意：不可以是大于等于，那样就不稳定了
24             {
25                 list2 = list2->next;
26                 list2_cur->next = list1_cur->next;
27                 list1_cur->next = list2_cur;
28                 list1_cur = list2_cur;
29                 list2_cur = list2;
30             }
31             else//后面一段list2的元素大于等于前面一段list1的元素时，前面一段指针直接后移
32                 list1_cur = list1_cur->next;
33         }
34         //后面一段list2中可能还有元素或NULL,总之把它接到list1后面
35         if(NULL == list1_cur->next)
36             list1_cur->next = list2_cur;
37         
38         ListNode* pHead = dummy->next;
39         delete dummy;//释放dummy
40         return pHead;//返回头结点
41     }
42 
43     //归并排序辅助函数(因为可能在头结点之前插入数据，故为ListNode** pHead)
44     ListNode* _list_merge_sort(ListNode** pHead)
45     {
46         if(NULL == *pHead || NULL == (*pHead)->next)
47             return *pHead;
48 
49         ListNode* pSlow = *pHead;
50         ListNode* pFast = *pHead;
51         while(pFast->next !=NULL && pFast->next->next !=NULL)
52         {
53             pSlow = pSlow->next;
54             pFast = pFast->next->next;
55         }
56 
57         ListNode* pLeftHead = *pHead;
58         ListNode* pRightHead = pSlow->next;
59         pSlow->next = NULL;//左半链表尾节点的next赋空值
60 
61         /*pLeftHead = */_list_merge_sort(&pLeftHead);
62         /*pRightHead = */_list_merge_sort(&pRightHead);
63 
64         //注意：虽然传值，但是内部状态可变，因此pLeftHead和pRightHead内部
65         //的的next可能已经变了，因此他们可能伸长或缩短
66         *pHead = list_merge(pLeftHead,pRightHead);//修改头指针
67         return *pHead;
68     }
69 public:
70     //归并排序入口，去掉了返回值，不包装这一层也行
71     void list_merge_sort(ListNode** pHead)
72     {
73         _list_merge_sort(pHead);//注意这里传入的是地址
74     }
75 };

完整测试程序：

  1 /*
  2 本程序说明：
  3 
  4 链表排序各种方法（快速排序）
  5 
  6 参考链接：
  7     http://blog.csdn.net/u012658346/article/details/51141288
  8     http://www.jb51.net/article/37300.htm
  9 
 10 */
 11 #include <iostream>
 12 using namespace std;
 13 
 14 
 15 //definition for singly-linked list.
 16 struct ListNode
 17 {
 18     int val;
 19     ListNode* next;
 20     ListNode(int x) : val(x), next(NULL) {}
 21 };
 22 
 23 //链表结点构造
 24 ListNode*  create_list_node(int val)
 25 {
 26     ListNode* pNode = new ListNode(val);
 27     return pNode;
 28 }
 29 //链表结点连接
 30 void connect_list_node(ListNode* pCur, ListNode* pNext)
 31 {
 32     pCur->next = pNext;
 33 }
 34 
 35 //销毁单个节点(其实用这个更好，不会出现空悬指针)
 36 void destory_Node(ListNode** ppNode)
 37 {
 38     if(*ppNode != NULL)
 39         delete *ppNode;
 40     *ppNode = NULL;
 41 }
 42 
 43 //链表销毁(注意，除头节点外，其他节点均变成了空悬指针)
 44 void destory_list(ListNode** ppHead)
 45 {
 46     ListNode** cur = ppHead;
 47     while(*cur != NULL)
 48     {
 49         ListNode* tmp = (*cur)->next;//保存下一个节点
 50         delete *cur;
 51         *cur = NULL;
 52         *cur = tmp;
 53     }
 54 }
 55 
 56 //链表打印
 57 void print_list(ListNode* pHead)
 58 {
 59     ListNode* cur = pHead;
 60     while(cur != NULL)
 61     {
 62         cout<< cur->val <<" ";
 63         cur = cur->next;
 64     }
 65     cout<<endl;
 66 }
 67 
 68 //链表快速排序
 69 class List_qsort
 70 {
 71 private:
 72     //交换元素
 73     void list_swap(int& lhs,int& rhs)
 74     {
 75         int tmp = lhs;
 76         lhs = rhs;
 77         rhs = tmp;
 78     }
 79     //划分，使左边小于头结点元素，右边大于等于头结点元素
 80     ListNode* list_partion(ListNode* pBegin,ListNode* pEnd)
 81     {
 82         if(pBegin == pEnd || pBegin->next == NULL)
 83             return pBegin;
 84 
 85         ListNode* pSlow=pBegin;
 86         ListNode* pFast=pBegin;
 87         int key=pBegin->val;
 88         while(pFast != pEnd)
 89         {
 90 
 91             if(pFast->val < key)
 92             {
 93                 pSlow = pSlow->next;
 94                 list_swap(pSlow->val,pFast->val);
 95             }
 96             pFast = pFast->next;
 97         }
 98 
 99         list_swap(pSlow->val,pBegin->val);
100 
101         return pSlow;
102     }
103     //排序辅助函数
104     void _list_qsort(ListNode* pBegin,ListNode* pEnd)
105     {
106         if(pBegin == pEnd || NULL == pBegin->next)
107             return;
108         ListNode* mid=list_partion(pBegin,pEnd);
109         _list_qsort(pBegin,mid);
110         _list_qsort(mid->next,pEnd);
111     }
112 public:    
113     //排序入口函数(版本1：传值)
114     void list_qsort(ListNode* pHead)
115     {
116         if(pHead == NULL || pHead->next ==NULL)
117             return ;
118         _list_qsort(pHead,NULL);
119 
120     }
121 
122     /*
123     //排序入口函数(版本2：传指针)
124     void list_qsort(ListNode** ppHead)
125     {
126         if(*ppHead == NULL || (*ppHead)->next ==NULL)
127             return;
128         _list_qsort(*ppHead,NULL);
129     }
130     */
131 
132     /*
133     //排序入口函数(版本3：传引用)
134     void list_qsort(ListNode*& pHead)
135     {
136         if(NULL == pHead  || NULL == pHead->next )
137             return;
138         _list_qsort(pHead,NULL);
139     }
140     */
141 };
142 
143 //链表插入排序
144 class List_insertion_sort
145 {
146 
147     //版本1：指针的指针
148 private:
149     //对于待插入的节点，选择合适的位置插入
150     void _list_insert_sort(ListNode** ppNode, ListNode *pNode)
151     {
152         ListNode* prev = NULL;
153         ListNode* cur = NULL;
154 
155         if(pNode->val < (*ppNode)->val)
156         {
157             pNode->next = *ppNode;
158             (*ppNode) = pNode;
159             return;
160         }
161 
162         cur = *ppNode;
163 
164         while(cur != NULL)
165         {
166             if(pNode->val < cur->val)
167                 break;
168 
169             prev = cur;
170             cur = cur->next;
171         }
172 
173         pNode->next = cur;//或pNode->next = prev->next
174         prev->next =pNode;
175         return;
176     }
177 public:
178     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
179     void list_insert_sort(ListNode** ppNode)
180     {
181         ListNode* prev = NULL;
182         ListNode* cur = NULL;
183 
184         if(NULL == ppNode || NULL == *ppNode)
185             return;
186 
187         cur = (*ppNode)->next;
188         (*ppNode)->next = NULL;
189 
190         while(cur != NULL)
191         {
192             prev = cur;
193             cur = cur->next;
194             _list_insert_sort(ppNode,prev);
195         }
196     }
197 
198     /*
199     //版本2：指针的引用
200 private:
201     //对于待插入的节点，选择合适的位置插入
202     void _list_insert_sort(ListNode*& ppNode, ListNode *pNode)
203     {
204         ListNode* prev = NULL;
205         ListNode* cur = NULL;
206 
207         if(pNode->val < ppNode->val)
208         {
209             pNode->next = ppNode;
210             ppNode = pNode;
211             return;
212         }
213 
214         cur = ppNode;
215 
216         while(cur != NULL)
217         {
218             if(pNode->val < cur->val)
219                 break;
220 
221             prev = cur;
222             cur = cur->next;
223         }
224 
225         pNode->next = cur;//或pNode->next = prev->next
226         prev->next =pNode;
227         return;
228     }
229 public:
230     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
231     void list_insert_sort(ListNode*& ppNode)
232     {
233         ListNode* prev = NULL;
234         ListNode* cur = NULL;
235 
236         if(NULL == ppNode)
237             return;
238 
239         cur = ppNode->next;
240         ppNode->next = NULL;
241 
242         while(cur != NULL)
243         {
244             prev = cur;
245             cur = cur->next;
246             _list_insert_sort(ppNode,prev);
247         }
248     }
249 */
250 
251 };
252 
253 
254 //链表归并排序
255 class List_merge_sort
256 {
257 private:
258     //合并两端链表
259     //因为可能在头结点之前插入数据，故为ListNode** list1
260     ListNode* list_merge(ListNode* list1, ListNode* list2)
261     {
262         if(NULL == list1)
263             return list2;
264         else if(NULL == list2)
265             return list1;
266 
267         ListNode* dummy = new ListNode(-1);//辅助头结点
268         dummy->next = list1;
269         ListNode* list1_cur = dummy;
270         ListNode* list2_cur = list2;
271 
272         while(list1_cur->next != NULL && list2_cur != NULL)
273         {
274             //cout<< list1_cur->next->val <<"==="<< list2_cur->val<<endl;
275             //把后面一段list2更小的元素插入前面一段list1中
276             if(list1_cur->next->val > list2_cur->val)//注意：不可以是大于等于，那样就不稳定了
277             {
278                 list2 = list2->next;
279                 list2_cur->next = list1_cur->next;
280                 list1_cur->next = list2_cur;
281                 list1_cur = list2_cur;
282                 list2_cur = list2;
283             }
284             else//后面一段list2的元素大于等于前面一段list1的元素时，前面一段指针直接后移
285                 list1_cur = list1_cur->next;
286         }
287         //后面一段list2中可能还有元素或NULL,总之把它接到list1后面
288         if(NULL == list1_cur->next)
289             list1_cur->next = list2_cur;
290         
291         ListNode* pHead = dummy->next;
292         delete dummy;//释放dummy
293         return pHead;//返回头结点
294 
295     }
296 
297     //归并排序辅助函数(因为可能在头结点之前插入数据，故为ListNode** pHead)
298     ListNode* _list_merge_sort(ListNode** pHead)
299     {
300         if(NULL == *pHead || NULL == (*pHead)->next)
301             return *pHead;
302 
303         ListNode* pSlow = *pHead;
304         ListNode* pFast = *pHead;
305         while(pFast->next !=NULL && pFast->next->next !=NULL)
306         {
307             pSlow = pSlow->next;
308             pFast = pFast->next->next;
309         }
310 
311         ListNode* pLeftHead = *pHead;
312         ListNode* pRightHead = pSlow->next;
313         pSlow->next = NULL;//左半链表尾节点的next赋空值
314 
315         /*pLeftHead = */_list_merge_sort(&pLeftHead);
316         /*pRightHead = */_list_merge_sort(&pRightHead);
317 
318         //注意：虽然传值，但是内部状态可变，因此pLeftHead和pRightHead内部
319         //的的next可能已经变了，因此他们可能伸长或缩短
320         *pHead = list_merge(pLeftHead,pRightHead);//修改头指针
321         return *pHead;
322     }
323 public:
324     //归并排序入口，去掉了返回值，不包装这一层也行
325     void list_merge_sort(ListNode** pHead)
326     {
327         _list_merge_sort(pHead);//注意这里传入的是地址
328     }
329 };
330 
331 //链表快速排序(测试样例)
332 void test_list_qsort()
333 {
334     //创建结点
335     ListNode* pNode1 = create_list_node(1);
336     ListNode* pNode2 = create_list_node(7);
337     ListNode* pNode3 = create_list_node(2);
338     ListNode* pNode4 =  create_list_node(6);
339     ListNode* pNode5 = create_list_node(-5);
340     ListNode* pNode6 = create_list_node(9);
341     ListNode* pNode7 = create_list_node(13);
342     ListNode* pNode8 = create_list_node(45);
343     ListNode* pNode9 = create_list_node(-7);
344 
345     //连接结点
346     connect_list_node(pNode1,pNode2);
347     connect_list_node(pNode2,pNode3);
348     connect_list_node(pNode3,pNode4);
349     connect_list_node(pNode4,pNode5);
350     connect_list_node(pNode5,pNode6);
351     connect_list_node(pNode6,pNode7);
352     connect_list_node(pNode7,pNode8);
353     connect_list_node(pNode8,pNode9);
354 
355     //打印链表
356     print_list(pNode1);
357 
358     //快速排序
359     List_qsort test_qsort;
360     test_qsort.list_qsort(pNode1);//传值
361     //test_qsort.list_qsort(&pNode1);//传指针
362     //test_qsort.list_qsort(pNode1);//传引用
363 
364     print_list(pNode1);
365 
366 /**********销毁链表(我们一般用到的方法，会出现空悬指针)********************/
367 //    destory_list(&pNode1);
368 //    //注意，释放链表后，头结点为NULL，其余的虽然释放了，但地址还在，因此成为空悬指针，需要进一步释放
369 //    //从这个角度来看，还不如写个函数释放每个节点,因此写了一个
370 
371 
372 //    if(pNode1)
373 //        print_list(pNode1);
374 //    else
375 //        cout<<"-1"<<endl;
376 /***********************************************************************/
377 
378 /****************销毁链表(逐个销毁，不会出现空悬指针)*********************/
379     destory_Node(&pNode1);
380     destory_Node(&pNode2);
381     destory_Node(&pNode3);
382     destory_Node(&pNode4);
383     destory_Node(&pNode5);
384     destory_Node(&pNode6);
385     destory_Node(&pNode7);
386     destory_Node(&pNode8);
387     destory_Node(&pNode9);
388     //    if(pNode1)
389     //        print_list(pNode1);
390     //    else
391     //        cout<<"-1"<<endl;
392 /***********************************************************************/
393 
394 }
395 
396 //链表插入排序(测试样例)
397 void test_list_insertion_sort()
398 {
399     //创建结点
400     ListNode* pNode1 = create_list_node(1);
401     ListNode* pNode2 = create_list_node(7);
402     ListNode* pNode3 = create_list_node(2);
403     ListNode* pNode4 =  create_list_node(6);
404     ListNode* pNode5 = create_list_node(-5);
405     ListNode* pNode6 = create_list_node(9);
406     ListNode* pNode7 = create_list_node(13);
407     ListNode* pNode8 = create_list_node(45);
408     ListNode* pNode9 = create_list_node(-7);
409 
410     //连接结点
411     connect_list_node(pNode1,pNode2);
412     connect_list_node(pNode2,pNode3);
413     connect_list_node(pNode3,pNode4);
414     connect_list_node(pNode4,pNode5);
415     connect_list_node(pNode5,pNode6);
416     connect_list_node(pNode6,pNode7);
417     connect_list_node(pNode7,pNode8);
418     connect_list_node(pNode8,pNode9);
419 
420     //打印链表
421     print_list(pNode1);
422 
423     //插入排序
424     List_insertion_sort test_insertion_sort;
425     test_insertion_sort.list_insert_sort(&pNode1);//传指针
426     //test_insertion_sort.list_insert_sort(pNode1);//传引用
427 
428     print_list(pNode1);
429 }
430 
431 //链表归并排序(测试样例)
432 void test_list_merge_sort()
433 {
434     //创建结点
435     ListNode* pNode1 = create_list_node(-11);
436     ListNode* pNode2 = create_list_node(-78);
437     ListNode* pNode3 = create_list_node(20);
438     ListNode* pNode4 = create_list_node(6);
439     ListNode* pNode5 = create_list_node(-5);
440     ListNode* pNode6 = create_list_node(9);
441     ListNode* pNode7 = create_list_node(-87);
442     ListNode* pNode8 = create_list_node(76);
443     //ListNode* pNode9 = create_list_node(-7);
444 
445     //连接结点
446     connect_list_node(pNode1,pNode2);
447     connect_list_node(pNode2,pNode3);
448     connect_list_node(pNode3,pNode4);
449     connect_list_node(pNode4,pNode5);
450     connect_list_node(pNode5,pNode6);
451     connect_list_node(pNode6,pNode7);
452     connect_list_node(pNode7,pNode8);
453     //connect_list_node(pNode8,pNode9);
454 
455     //打印链表
456     print_list(pNode1);
457 
458     //归并排序
459     List_merge_sort test_merge_sort;
460     //ListNode* p=test_merge_sort.list_merge_sort(&pNode1);//传指针
461     test_merge_sort.list_merge_sort(&pNode1);
462 
463     print_list(pNode1);
464 }
465 
466 
467 int main()
468 {
469     cout<<"测试程序："<<endl<<endl;
470     cout<<"链表快速排序："<<endl;
471     test_list_qsort();
472     cout<<endl;
473     cout<<"链表插入排序："<<endl;
474     test_list_insertion_sort();
475     cout<<endl;
476     cout<<"链表归并排序："<<endl;
477     test_list_merge_sort();
478     cout<<endl;
479     return 0;
480 
481     return 0;
482 }

View Code

二、模板版本（适用性广泛）

文中链表定义：

1 //definition for singly-linked list.
2 template <typename T>
3 struct ListNode
4 {
5     T val;
6     ListNode<T>* next;
7     ListNode(T x) : val(x), next(NULL) {}
8 };

链表相关操作：

//链表结点构造
template <typename T>
ListNode<T>*  create_list_node(T val)
{
    ListNode<T>* pNode = new ListNode<T>(val);
    return pNode;
}

//链表结点连接
template <typename T>
void connect_list_node(ListNode<T>* pCur, ListNode<T>* pNext)
{
    pCur->next = pNext;
}

//销毁单个节点(其实用这个更好，不会出现空悬指针)
template <typename T>
void destory_Node(ListNode<T>** ppNode)
{
    if(*ppNode != NULL)
        delete *ppNode;
    *ppNode = NULL;
}

//链表销毁(注意，除头节点外，其他节点均变成了空悬指针，不建议此种方法)
template <typename T>
void destory_list(ListNode<T>** ppHead)
{
    ListNode<T>** cur = ppHead;
    while(*cur != NULL)
    {
        ListNode<T>* tmp = (*cur)->next;//保存下一个节点
        delete *cur;
        *cur = NULL;
        *cur = tmp;
    }
}

//链表打印
template <typename T>
void print_list(ListNode<T>* pHead)
{
    ListNode<T>* cur = pHead;
    while(cur != NULL)
    {
        cout<< cur->val <<" ";
        cur = cur->next;
    }
    cout<<endl;
}

三种排序方法：

 1 //链表快速排序
 2 template <typename T>
 3 class List_qsort
 4 {
 5 private:
 6     //划分，使左边小于头结点元素，右边大于等于头结点元素
 7     ListNode<T>* list_partion(ListNode<T>* pBegin,ListNode<T>* pEnd)
 8     {
 9         if(pBegin == pEnd || pBegin->next == NULL)
10             return pBegin;
11 
12         ListNode<T>* pSlow=pBegin;
13         ListNode<T>* pFast=pBegin;
14         ListNode<T>* pKey=new ListNode<T>(pBegin->val);//只为了保存用于比较的val
15         while(pFast != pEnd)
16         {
17 
18             if(pFast->val < pKey->val)
19             {
20                 pSlow = pSlow->next;
21                 swap(pSlow->val,pFast->val);
22             }
23             pFast = pFast->next;
24         }
25 
26         swap(pSlow->val,pBegin->val);
27         delete pKey;//释放pKey
28         return pSlow;
29     }
30     //排序辅助函数
31     void _list_qsort(ListNode<T>* pBegin,ListNode<T>* pEnd)
32     {
33         if(pBegin == pEnd || NULL == pBegin->next)
34             return;
35         ListNode<T>* mid=list_partion(pBegin,pEnd);
36         _list_qsort(pBegin,mid);
37         _list_qsort(mid->next,pEnd);
38     }
39 public:    
40     //排序入口函数(版本1：传值)
41     void list_qsort(ListNode<T>* pHead)
42     {
43         if(pHead == NULL || pHead->next ==NULL)
44             return ;
45         _list_qsort(pHead,NULL);
46 
47     }
48 
49     /*
50     //排序入口函数(版本2：传指针)
51     void list_qsort(ListNode<T>** ppHead)
52     {
53         if(*ppHead == NULL || (*ppHead)->next ==NULL)
54             return;
55         _list_qsort(*ppHead,NULL);
56     }
57     */
58 
59     /*
60     //排序入口函数(版本3：传引用)
61     void list_qsort(ListNode<T>*& pHead)
62     {
63         if(NULL == pHead  || NULL == pHead->next )
64             return;
65         _list_qsort(pHead,NULL);
66     }
67     */
68 };

  1 //链表插入排序
  2 template <typename T>
  3 class List_insertion_sort
  4 {
  5 
  6     //版本1：指针的指针
  7 private:
  8     //对于待插入的节点，选择合适的位置插入
  9     void _list_insert_sort(ListNode<T>** ppNode, ListNode<T>* pNode)
 10     {
 11         ListNode<T>* prev = NULL;
 12         ListNode<T>* cur = NULL;
 13 
 14         if(pNode->val < (*ppNode)->val)
 15         {
 16             pNode->next = *ppNode;
 17             (*ppNode) = pNode;
 18             return;
 19         }
 20 
 21         cur = *ppNode;
 22 
 23         while(cur != NULL)
 24         {
 25             if(pNode->val < cur->val)
 26                 break;
 27 
 28             prev = cur;
 29             cur = cur->next;
 30         }
 31 
 32         pNode->next = cur;//或pNode->next = prev->next
 33         prev->next =pNode;
 34         return;
 35     }
 36 public:
 37     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
 38     void list_insert_sort(ListNode<T>** ppNode)
 39     {
 40         ListNode<T>* prev = NULL;
 41         ListNode<T>* cur = NULL;
 42 
 43         if(NULL == ppNode || NULL == *ppNode)
 44             return;
 45 
 46         cur = (*ppNode)->next;
 47         (*ppNode)->next = NULL;
 48 
 49         while(cur != NULL)
 50         {
 51             prev = cur;
 52             cur = cur->next;
 53             _list_insert_sort(ppNode,prev);
 54         }
 55     }
 56 
 57     /*
 58     //版本2：指针的引用
 59 private:
 60     //对于待插入的节点，选择合适的位置插入
 61     void _list_insert_sort(ListNode<T>*& ppNode, ListNode<T> *pNode)
 62     {
 63         ListNode<T>* prev = NULL;
 64         ListNode<T>* cur = NULL;
 65 
 66         if(pNode->val < ppNode->val)
 67         {
 68             pNode->next = ppNode;
 69             ppNode = pNode;
 70             return;
 71         }
 72 
 73         cur = ppNode;
 74 
 75         while(cur != NULL)
 76         {
 77             if(pNode->val < cur->val)
 78                 break;
 79 
 80             prev = cur;
 81             cur = cur->next;
 82         }
 83 
 84         pNode->next = cur;//或pNode->next = prev->next
 85         prev->next =pNode;
 86         return;
 87     }
 88 public:
 89     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
 90     void list_insert_sort(ListNode<T>*& ppNode)
 91     {
 92         ListNode<T>* prev = NULL;
 93         ListNode<T>* cur = NULL;
 94 
 95         if(NULL == ppNode)
 96             return;
 97 
 98         cur = ppNode->next;
 99         ppNode->next = NULL;
100 
101         while(cur != NULL)
102         {
103             prev = cur;
104             cur = cur->next;
105             _list_insert_sort(ppNode,prev);
106         }
107     }
108 */
109 
110 };

 1 //链表归并排序
 2 template <typename T>
 3 class List_merge_sort
 4 {
 5 private:
 6     //合并两端链表
 7     //因为可能在头结点之前插入数据，故为ListNode<T>** list1
 8     ListNode<T>* list_merge(ListNode<T>* list1, ListNode<T>* list2)
 9     {
10         if(NULL == list1)
11             return list2;
12         else if(NULL == list2)
13             return list1;
14 
15         ListNode<T>* dummy = new ListNode<T>(-1);//辅助头结点
16         dummy->next = list1;
17         ListNode<T>* list1_cur = dummy;
18         ListNode<T>* list2_cur = list2;
19 
20         while(list1_cur->next != NULL && list2_cur != NULL)
21         {
22             //cout<< list1_cur->next->val <<"==="<< list2_cur->val<<endl;
23             //把后面一段list2更小的元素插入前面一段list1中
24             if(list1_cur->next->val > list2_cur->val)//注意：不可以是大于等于，那样就不稳定了
25             {
26                 list2 = list2->next;
27                 list2_cur->next = list1_cur->next;
28                 list1_cur->next = list2_cur;
29                 list1_cur = list2_cur;
30                 list2_cur = list2;
31             }
32             else//后面一段list2的元素大于等于前面一段list1的元素时，前面一段指针直接后移
33                 list1_cur = list1_cur->next;
34         }
35         //后面一段list2中可能还有元素或NULL,总之把它接到list1后面
36         if(NULL == list1_cur->next)
37             list1_cur->next = list2_cur;
38 
39         ListNode<T>* pHead = dummy->next;
40         delete dummy;//释放dummy
41         return pHead;//返回头结点
42     }
43 
44     //归并排序辅助函数(因为可能在头结点之前插入数据，故为ListNode<T>** pHead)
45     ListNode<T>* _list_merge_sort(ListNode<T>** pHead)
46     {
47         if(NULL == *pHead || NULL == (*pHead)->next)
48             return *pHead;
49 
50         ListNode<T>* pSlow = *pHead;
51         ListNode<T>* pFast = *pHead;
52         while(pFast->next !=NULL && pFast->next->next !=NULL)
53         {
54             pSlow = pSlow->next;
55             pFast = pFast->next->next;
56         }
57 
58         ListNode<T>* pLeftHead = *pHead;
59         ListNode<T>* pRightHead = pSlow->next;
60         pSlow->next = NULL;//左半链表尾节点的next赋空值
61 
62         /*pLeftHead = */_list_merge_sort(&pLeftHead);
63         /*pRightHead = */_list_merge_sort(&pRightHead);
64 
65         //注意：虽然传值，但是内部状态可变，因此pLeftHead和pRightHead内部
66         //的的next可能已经变了，因此他们可能伸长或缩短
67         *pHead = list_merge(pLeftHead,pRightHead);//修改头指针
68         return *pHead;
69     }
70 public:
71     //归并排序入口，去掉了返回值，不包装这一层也行
72     void list_merge_sort(ListNode<T>** pHead)
73     {
74         _list_merge_sort(pHead);//注意这里传入的是地址
75     }
76 };

完整测试程序：

  1 /*
  2 本程序说明：
  3 
  4 链表排序各种方法（快速排序）
  5 
  6 参考链接：
  7     http://blog.csdn.net/u012658346/article/details/51141288
  8     http://www.jb51.net/article/37300.htm
  9 
 10 */
 11 #include <iostream>
 12 using namespace std;
 13 
 14 
 15 //definition for singly-linked list.
 16 template <typename T>
 17 struct ListNode
 18 {
 19     T val;
 20     ListNode<T>* next;
 21     ListNode(T x) : val(x), next(NULL) {}
 22 };
 23 
 24 //链表结点构造
 25 template <typename T>
 26 ListNode<T>*  create_list_node(T val)
 27 {
 28     ListNode<T>* pNode = new ListNode<T>(val);
 29     return pNode;
 30 }
 31 
 32 //链表结点连接
 33 template <typename T>
 34 void connect_list_node(ListNode<T>* pCur, ListNode<T>* pNext)
 35 {
 36     pCur->next = pNext;
 37 }
 38 
 39 //销毁单个节点(其实用这个更好，不会出现空悬指针)
 40 template <typename T>
 41 void destory_Node(ListNode<T>** ppNode)
 42 {
 43     if(*ppNode != NULL)
 44         delete *ppNode;
 45     *ppNode = NULL;
 46 }
 47 
 48 //链表销毁(注意，除头节点外，其他节点均变成了空悬指针)
 49 template <typename T>
 50 void destory_list(ListNode<T>** ppHead)
 51 {
 52     ListNode<T>** cur = ppHead;
 53     while(*cur != NULL)
 54     {
 55         ListNode<T>* tmp = (*cur)->next;//保存下一个节点
 56         delete *cur;
 57         *cur = NULL;
 58         *cur = tmp;
 59     }
 60 }
 61 
 62 //链表打印
 63 template <typename T>
 64 void print_list(ListNode<T>* pHead)
 65 {
 66     ListNode<T>* cur = pHead;
 67     while(cur != NULL)
 68     {
 69         cout<< cur->val <<" ";
 70         cur = cur->next;
 71     }
 72     cout<<endl;
 73 }
 74 
 75 //链表快速排序
 76 template <typename T>
 77 class List_qsort
 78 {
 79 private:
 80     //划分，使左边小于头结点元素，右边大于等于头结点元素
 81     ListNode<T>* list_partion(ListNode<T>* pBegin,ListNode<T>* pEnd)
 82     {
 83         if(pBegin == pEnd || pBegin->next == NULL)
 84             return pBegin;
 85 
 86         ListNode<T>* pSlow=pBegin;
 87         ListNode<T>* pFast=pBegin;
 88         ListNode<T>* pKey=new ListNode<T>(pBegin->val);//只为了保存用于比较的val
 89         while(pFast != pEnd)
 90         {
 91 
 92             if(pFast->val < pKey->val)
 93             {
 94                 pSlow = pSlow->next;
 95                 swap(pSlow->val,pFast->val);
 96             }
 97             pFast = pFast->next;
 98         }
 99 
100         swap(pSlow->val,pBegin->val);
101         delete pKey;//释放pKey
102         return pSlow;
103     }
104     //排序辅助函数
105     void _list_qsort(ListNode<T>* pBegin,ListNode<T>* pEnd)
106     {
107         if(pBegin == pEnd || NULL == pBegin->next)
108             return;
109         ListNode<T>* mid=list_partion(pBegin,pEnd);
110         _list_qsort(pBegin,mid);
111         _list_qsort(mid->next,pEnd);
112     }
113 public:    
114     //排序入口函数(版本1：传值)
115     void list_qsort(ListNode<T>* pHead)
116     {
117         if(pHead == NULL || pHead->next ==NULL)
118             return ;
119         _list_qsort(pHead,NULL);
120 
121     }
122 
123     /*
124     //排序入口函数(版本2：传指针)
125     void list_qsort(ListNode<T>** ppHead)
126     {
127         if(*ppHead == NULL || (*ppHead)->next ==NULL)
128             return;
129         _list_qsort(*ppHead,NULL);
130     }
131     */
132 
133     /*
134     //排序入口函数(版本3：传引用)
135     void list_qsort(ListNode<T>*& pHead)
136     {
137         if(NULL == pHead  || NULL == pHead->next )
138             return;
139         _list_qsort(pHead,NULL);
140     }
141     */
142 };
143 
144 //链表插入排序
145 template <typename T>
146 class List_insertion_sort
147 {
148 
149     //版本1：指针的指针
150 private:
151     //对于待插入的节点，选择合适的位置插入
152     void _list_insert_sort(ListNode<T>** ppNode, ListNode<T>* pNode)
153     {
154         ListNode<T>* prev = NULL;
155         ListNode<T>* cur = NULL;
156 
157         if(pNode->val < (*ppNode)->val)
158         {
159             pNode->next = *ppNode;
160             (*ppNode) = pNode;
161             return;
162         }
163 
164         cur = *ppNode;
165 
166         while(cur != NULL)
167         {
168             if(pNode->val < cur->val)
169                 break;
170 
171             prev = cur;
172             cur = cur->next;
173         }
174 
175         pNode->next = cur;//或pNode->next = prev->next
176         prev->next =pNode;
177         return;
178     }
179 public:
180     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
181     void list_insert_sort(ListNode<T>** ppNode)
182     {
183         ListNode<T>* prev = NULL;
184         ListNode<T>* cur = NULL;
185 
186         if(NULL == ppNode || NULL == *ppNode)
187             return;
188 
189         cur = (*ppNode)->next;
190         (*ppNode)->next = NULL;
191 
192         while(cur != NULL)
193         {
194             prev = cur;
195             cur = cur->next;
196             _list_insert_sort(ppNode,prev);
197         }
198     }
199 
200     /*
201     //版本2：指针的引用
202 private:
203     //对于待插入的节点，选择合适的位置插入
204     void _list_insert_sort(ListNode<T>*& ppNode, ListNode<T> *pNode)
205     {
206         ListNode<T>* prev = NULL;
207         ListNode<T>* cur = NULL;
208 
209         if(pNode->val < ppNode->val)
210         {
211             pNode->next = ppNode;
212             ppNode = pNode;
213             return;
214         }
215 
216         cur = ppNode;
217 
218         while(cur != NULL)
219         {
220             if(pNode->val < cur->val)
221                 break;
222 
223             prev = cur;
224             cur = cur->next;
225         }
226 
227         pNode->next = cur;//或pNode->next = prev->next
228         prev->next =pNode;
229         return;
230     }
231 public:
232     //首先遍历节点，一边是排序好的节点，一边是待排序的节点
233     void list_insert_sort(ListNode<T>*& ppNode)
234     {
235         ListNode<T>* prev = NULL;
236         ListNode<T>* cur = NULL;
237 
238         if(NULL == ppNode)
239             return;
240 
241         cur = ppNode->next;
242         ppNode->next = NULL;
243 
244         while(cur != NULL)
245         {
246             prev = cur;
247             cur = cur->next;
248             _list_insert_sort(ppNode,prev);
249         }
250     }
251 */
252 
253 };
254 
255 
256 //链表归并排序
257 template <typename T>
258 class List_merge_sort
259 {
260 private:
261     //合并两端链表
262     //因为可能在头结点之前插入数据，故为ListNode<T>** list1
263     ListNode<T>* list_merge(ListNode<T>* list1, ListNode<T>* list2)
264     {
265         if(NULL == list1)
266             return list2;
267         else if(NULL == list2)
268             return list1;
269 
270         ListNode<T>* dummy = new ListNode<T>(-1);//辅助头结点
271         dummy->next = list1;
272         ListNode<T>* list1_cur = dummy;
273         ListNode<T>* list2_cur = list2;
274 
275         while(list1_cur->next != NULL && list2_cur != NULL)
276         {
277             //cout<< list1_cur->next->val <<"==="<< list2_cur->val<<endl;
278             //把后面一段list2更小的元素插入前面一段list1中
279             if(list1_cur->next->val > list2_cur->val)//注意：不可以是大于等于，那样就不稳定了
280             {
281                 list2 = list2->next;
282                 list2_cur->next = list1_cur->next;
283                 list1_cur->next = list2_cur;
284                 list1_cur = list2_cur;
285                 list2_cur = list2;
286             }
287             else//后面一段list2的元素大于等于前面一段list1的元素时，前面一段指针直接后移
288                 list1_cur = list1_cur->next;
289         }
290         //后面一段list2中可能还有元素或NULL,总之把它接到list1后面
291         if(NULL == list1_cur->next)
292             list1_cur->next = list2_cur;
293 
294         ListNode<T>* pHead = dummy->next;
295         delete dummy;//释放dummy
296         return pHead;//返回头结点
297     }
298 
299     //归并排序辅助函数(因为可能在头结点之前插入数据，故为ListNode<T>** pHead)
300     ListNode<T>* _list_merge_sort(ListNode<T>** pHead)
301     {
302         if(NULL == *pHead || NULL == (*pHead)->next)
303             return *pHead;
304 
305         ListNode<T>* pSlow = *pHead;
306         ListNode<T>* pFast = *pHead;
307         while(pFast->next !=NULL && pFast->next->next !=NULL)
308         {
309             pSlow = pSlow->next;
310             pFast = pFast->next->next;
311         }
312 
313         ListNode<T>* pLeftHead = *pHead;
314         ListNode<T>* pRightHead = pSlow->next;
315         pSlow->next = NULL;//左半链表尾节点的next赋空值
316 
317         /*pLeftHead = */_list_merge_sort(&pLeftHead);
318         /*pRightHead = */_list_merge_sort(&pRightHead);
319 
320         //注意：虽然传值，但是内部状态可变，因此pLeftHead和pRightHead内部
321         //的的next可能已经变了，因此他们可能伸长或缩短
322         *pHead = list_merge(pLeftHead,pRightHead);//修改头指针
323         return *pHead;
324     }
325 public:
326     //归并排序入口，去掉了返回值，不包装这一层也行
327     void list_merge_sort(ListNode<T>** pHead)
328     {
329         _list_merge_sort(pHead);//注意这里传入的是地址
330     }
331 };
332 
333 //链表快速排序(测试样例)
334 void test_list_qsort()
335 {
336     //创建结点
337     ListNode<double>* pNode1 = create_list_node<double>(1.8);
338     ListNode<double>* pNode2 = create_list_node<double>(7.3);
339     ListNode<double>* pNode3 = create_list_node<double>(2.6);
340     ListNode<double>* pNode4 = create_list_node<double>(6);
341     ListNode<double>* pNode5 = create_list_node<double>(-5.8);
342     ListNode<double>* pNode6 = create_list_node<double>(99.5);
343     ListNode<double>* pNode7 = create_list_node<double>(13);
344     ListNode<double>* pNode8 = create_list_node<double>(45);
345     ListNode<double>* pNode9 = create_list_node<double>(-7);
346 
347     //连接结点
348     connect_list_node(pNode1,pNode2);
349     connect_list_node(pNode2,pNode3);
350     connect_list_node(pNode3,pNode4);
351     connect_list_node(pNode4,pNode5);
352     connect_list_node(pNode5,pNode6);
353     connect_list_node(pNode6,pNode7);
354     connect_list_node(pNode7,pNode8);
355     connect_list_node(pNode8,pNode9);
356 
357     //打印链表
358     cout<<"原链表: ";print_list(pNode1);
359 
360     //快速排序
361     List_qsort<double> test_qsort;
362     test_qsort.list_qsort(pNode1);//传值
363     //test_qsort.list_qsort(&pNode1);//传指针
364     //test_qsort.list_qsort(pNode1);//传引用
365 
366     cout<<"排序后: ";print_list(pNode1);
367 
368 /**********销毁链表(我们一般用到的方法，会出现空悬指针)********************/
369 //    destory_list(&pNode1);
370 //    //注意，释放链表后，头结点为NULL，其余的虽然释放了，但地址还在，因此成为空悬指针，需要进一步释放
371 //    //从这个角度来看，还不如写个函数释放每个节点,因此写了一个
372 
373 
374 //    if(pNode1)
375 //        print_list(pNode1);
376 //    else
377 //        cout<<"-1"<<endl;
378 /***********************************************************************/
379 
380 /****************销毁链表(逐个销毁，不会出现空悬指针)*********************/
381     destory_Node(&pNode1);
382     destory_Node(&pNode2);
383     destory_Node(&pNode3);
384     destory_Node(&pNode4);
385     destory_Node(&pNode5);
386     destory_Node(&pNode6);
387     destory_Node(&pNode7);
388     destory_Node(&pNode8);
389     destory_Node(&pNode9);
390     //    if(pNode1)
391     //        print_list(pNode1);
392     //    else
393     //        cout<<"-1"<<endl;
394 /***********************************************************************/
395 
396 }
397 
398 //链表插入排序(测试样例)
399 void test_list_insertion_sort()
400 {
401     //创建结点
402     ListNode<double>* pNode1 = create_list_node<double>(1.8);
403     ListNode<double>* pNode2 = create_list_node<double>(7.3);
404     ListNode<double>* pNode3 = create_list_node<double>(2.6);
405     ListNode<double>* pNode4 = create_list_node<double>(6);
406     ListNode<double>* pNode5 = create_list_node<double>(-5.8);
407     ListNode<double>* pNode6 = create_list_node<double>(99.5);
408     ListNode<double>* pNode7 = create_list_node<double>(13);
409     ListNode<double>* pNode8 = create_list_node<double>(45);
410     ListNode<double>* pNode9 = create_list_node<double>(-7);
411 
412     //连接结点
413     connect_list_node(pNode1,pNode2);
414     connect_list_node(pNode2,pNode3);
415     connect_list_node(pNode3,pNode4);
416     connect_list_node(pNode4,pNode5);
417     connect_list_node(pNode5,pNode6);
418     connect_list_node(pNode6,pNode7);
419     connect_list_node(pNode7,pNode8);
420     connect_list_node(pNode8,pNode9);
421 
422     //打印链表
423     cout<<"原链表: ";print_list(pNode1);
424 
425     //插入排序
426     List_insertion_sort<double> test_insertion_sort;
427     test_insertion_sort.list_insert_sort(&pNode1);//传指针
428     //test_insertion_sort.list_insert_sort(pNode1);//传引用
429 
430     cout<<"排序后: ";print_list(pNode1);
431 }
432 
433 //链表归并排序(测试样例)
434 void test_list_merge_sort()
435 {
436     //创建结点
437     ListNode<double>* pNode1 = create_list_node<double>(1.8);
438     ListNode<double>* pNode2 = create_list_node<double>(7.3);
439     ListNode<double>* pNode3 = create_list_node<double>(2.6);
440     ListNode<double>* pNode4 = create_list_node<double>(6);
441     ListNode<double>* pNode5 = create_list_node<double>(-5.8);
442     ListNode<double>* pNode6 = create_list_node<double>(99.5);
443     ListNode<double>* pNode7 = create_list_node<double>(13);
444     ListNode<double>* pNode8 = create_list_node<double>(45);
445     ListNode<double>* pNode9 = create_list_node<double>(-7);
446 
447     //连接结点
448     connect_list_node(pNode1,pNode2);
449     connect_list_node(pNode2,pNode3);
450     connect_list_node(pNode3,pNode4);
451     connect_list_node(pNode4,pNode5);
452     connect_list_node(pNode5,pNode6);
453     connect_list_node(pNode6,pNode7);
454     connect_list_node(pNode7,pNode8);
455     connect_list_node(pNode8,pNode9);
456 
457     //打印链表
458     cout<<"原链表: ";print_list(pNode1);
459 
460     //归并排序
461     List_merge_sort<double> test_merge_sort;
462     //ListNode<double>* p=test_merge_sort.list_merge_sort(&pNode1);//传指针
463     test_merge_sort.list_merge_sort(&pNode1);
464 
465     cout<<"排序后: ";print_list(pNode1);
466 }
467 
468 
469 int main()
470 {
471     cout<<"测试程序："<<endl<<endl;
472     cout<<"链表快速排序："<<endl;
473     test_list_qsort();
474     cout<<endl;
475     cout<<"链表插入排序："<<endl;
476     test_list_insertion_sort();
477     cout<<endl;
478     cout<<"链表归并排序："<<endl;
479     test_list_merge_sort();
480     cout<<endl;
481     return 0;
482 }

View Code

总结

链表的操作都基于指针，我们可以通过编写其各种排序代码练习对指针的操作，如指针的指针，指针的引用等。

另外，我这里只是演示了三种排序方法，如果有错误敬请指正。大家可试试编写几种其他的排序方法。

参考文章

单链表排序----快排 & 归并排序http://blog.csdn.net/u012658346/article/details/51141288
深入单链表的快速排序详解 http://www.jb51.net/article/37300.htm
一步一步写算法（之链表排序）http://blog.csdn.net/feixiaoxing/article/details/6905260/
算法题——单链表的归并排序http://www.cnblogs.com/qieerbushejinshikelou/archive/2014/08/17/3917302.html

在此对以上文章作者表示感谢。欢迎交流。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有