本文章整理了链表排序的三种方法,分别是快速排序、插入排序、归并排序。为适应不同用途,先给出常用的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 }
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 }
链表的操作都基于指针,我们可以通过编写其各种排序代码练习对指针的操作,如指针的指针,指针的引用等。
另外,我这里只是演示了三种排序方法,如果有错误敬请指正。大家可试试编写几种其他的排序方法。
在此对以上文章作者表示感谢。欢迎交流。