链表定义及主函数
1、list.h文件
1、 #ifndef _LIST_H_
2、 #define _LIST_H_
3、
4、 struct ListNode
5、 {
6、 int val;
7、 ListNode* next;
8、 };
9、
10、#endif
2、main.cpp（省去链表排序代码）
1. #include <iostream>
2.
3. using namespace std;
4.
5. #include "List.h"
6.
7. void InsertionSortList();
8. void SelectSortList();
9.
10. //构建链表头结点
11. ListNode* head = new ListNode;
12.
13. int main()
14. {
15. head->next = NULL;
16.
17. //对链表赋值
18. for (int i = 0; i < 10; ++i)
19. {
20.
21. ListNode* p = new ListNode;
22. cin >> p->val;
23. p->next = head->next;
24. head->next = p;
25.
26. }
27.
28. //这里填写链表排序函数，如下：
29. //InsertionSortList();
30. SelectSortList();
31.
32. ListNode* q = head->next;
33. while (q)
34. {
35. cout << q->val << ' ';
36. q = q->next;
37. }
38.
39. return 0;
40. }
一、交换结点
1、直接插入排序
假设排序规则为从小到大。
左边的有序区为：head – pend的区域
右边的无序区为：p – NULL的区域
每次从head->next开始，tmp = head->next; 比较tmp->val与p->val和tmp与p的关系。
pre为tmp的前缀节点。
当tmp->val < p->val时，tmp、pre一直向后移；
当tmp->val > p->val时，将tmp与p两结点交换；
当tmp == p时，说明head – p为有序区，将pend = p。
插入排序在链表应用中
交换结点
。
二、交换元素
1、选择排序
假设排序规则由小到大。
将待排序列分为有序序列与无序序列。
每次在无序序列中找到最小的元素，将其与有序序列的最后一个值进行交换。
选择排序在链表应用中
交换元素
而不交换节点。
2、快速排序
单链表的快排序和数组的快排序基本思想相同，同样是基于划分，但是又有很大的不同：
单链表不支持基于下标的访问。
故算法中把待排序的链表拆分为
2
个子链表。
为了简单起见，选择
链表的第一个节点作为基准
，然后进行比较，比基准小得节点放入左面的子链表，比基准大的放入右边的子链表。在对待排序链表扫描一遍之后，左边子链表的节点值都小于基准的值，右边子链表的值都大于基准的值，然后把基准插入到链表中，并作为连接两个子链表的桥梁。然后分别对左、右两个子链表进行递归快速排序，以提高性能。
但是，由于单链表不能像数组那样随机存储，和数组的快排序相比较，还是有一些需要注意的细节：
1
、支点的选取，由于不能随机访问第
K
个元素，因此每次选择支点时可以取待排序那部分链表的头指针；
2
、遍历量表方式，由于不能从单链表的末尾向前遍历，因此使用两个指针分别向前向后遍历的策略失效。
事实上，可以采用一趟遍历的方式将较小的元素放到单链表的左边。
具体方法为：
1)
定义两个指针
pslow
，
pfast
，其中
pslow
指向单链表的头结点，
pfast
指向单链表头结点的下一个结点
;
2)
使用
pfast
遍历单链表，每遇到一个比支点小的元素，就令
pslow=pslow->next
，然后和
pslow
进行数据交换。
3)
、交换数据方式，直接交换链表数据指针指向的部分，不必交换链表节点本身。
链表快速排序描述来源：
深入单链表的快速排序详解