单链表排序（快排方法）_单链表快速排序算法

原文
说一下我的理解：
是传统快排的变种;
传统快排：

基准 小 小 小 小 小 　未排 未排 未排 未排 　大 大 大 大 大
　　　　　　　　　　L->　　　　　<- R
L,R相向而行，即R向左走找比基准小的， L向右走找比基准大的，交换，相遇时结束。

但对于链表，L向右当然是可以的，但R向左，就要额外存储pre，或者频繁的单向遍历。
那怎样利用快排思想又不用额外存储或频繁遍历呢？，可以这样，换种指针走向：

基准 小 小 小 小 小　　大 大 大 大 大　 未排 未排 未排 未排
　　　　　　　Ｌ->　　　　　　　　　Ｒ->
R和L都向右走，R先走，找到比基准小的后，Ｌ向前走一步，交换，直到Ｒ走到末尾。

一句话概括：链表的快排就是在左右指针间维护比基准数大的窗口。
而传统快排里，左右指针间是未排序的。

#include <iostream>
using namespace std;
/*
题目：链式存储的快排
作者：伊特玛德神
算法思想：
每一趟以第一个元素为基准
q依次后移，若小于基准，则与p交换
p与q之间的维持大于基准的元素
最后将基准与p交换
此时基准左边是小于的链表，右边是大于的
然后进行下一趟
快排左边和右边的链表
*/
typedef struct node {
	int val;
	node* next;
}node;
 
void my_swap(node* p, node* q) {
	// 自写交换函数
	// 只交换值，不更改链表指针，减少执行时间
    // 这里如果想交换指针，就需要增加前驱，麻烦点而已
	int tmp = p->val;
	p->val = q->val;
	q->val = tmp;
}
 
void quick_sort_list(node* head, node* tail) {
	if (head == tail || head == NULL || head == tail->next)return; // 递归出口
	node* p, * q, * pre;
	p = q = pre = head;
	while (q != tail) {
		q = q->next; // 对于一个链表只遍历一遍
		if (q->val < head->val) {
			// 如果q的值大于base则放在p左边
			pre = p;
			p = p->next;
			my_swap(p, q);
		}
	}// 执行while完毕后的情况：
	// base在head,[head->next,p]小于base,[p->next,tail]大于base
	my_swap(head, p); // 将base放在最终位置
	quick_sort_list(head, pre);
	quick_sort_list(p->next, tail);
}
 
int main(){
	node* List = new node;//带头结点的链表
	node* p = List;
	int n = 0;
	cout << "要输入几个数字？" << endl;
	cin >> n;
	for (short i = 0; i < n; i++) {
		node* q = new node;
		cin >> q->val;
		q->next = NULL;
		p->next = q; p = q;		
	}
	quick_sort_list(List->next, p);
	p = List -> next;
	while (p != NULL) {
		cout << p->val << " ";
		p = p->next;
	}
	cout << "执行结束" << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68