待排序列采用带头结点的单链表，请写出在其上进行快速排序的递归算法。_若待排序列用带头结点的单链表存储,试给出简单选择排序算法

#include <iostream>
using namespace std;

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode;

/*
	带头结点的链表有元素如下
	[23, 17, 45, 21, 6, 14, 56, 50]
	现在要对链表元素进行快速排序
	设原始链表的元素顺序和上述的数组的顺序一致；
*/

void createList(LNode *p, int *R, int n)	//生成单链表
{	
	p->next = NULL;
	LNode *q;
	for (int i = n - 1; i >= 0; --i)
	{
		q = (LNode*)malloc(sizeof(LNode));
		q->data = R[i];
		q->next = p->next;
		p->next = q;
	}
}

void printList(LNode *p)
{	
	if (p == NULL)
		return;
	LNode *q = p->next;
	while (q != NULL)
	{
		cout << q->data << endl;
		q = q->next;
	}
}
void quickSort(LNode *first, LNode *end) //first是指向第一个结点的指针
{
	if (first == NULL || first == end)
		return;
	LNode *p1, *p2;	//定义俩个辅助指针
	/*
		p1指向左子链的最右端，p1
		而p2一直向右移动，如果p2所指值小于基准值，把p1先向右移动一个，然后交换p1和p2的data
	
	*/
	p1 = first;
	p2 = first->next;
	while (p2 != end)
	{
		if (p2->data < first->data)  //小于基准值
		{
			p1 = p1->next;
			int temp = p2->data;
			p2->data = p1->data;
			p1->data = temp;
		}
		p2 = p2->next;
	}
	//p1成为了左子链的最右的一个结点
	//需要交换p1和基准结点的值，交换后满足了基准结点在中间，它的左侧值都比它小
	int temp = p1->data;
	p1->data = first->data;
	first->data = temp;
	quickSort(first, p1);
	quickSort(p1->next, end);
}

int main()
{
	
	LNode *head;
	int R[] = {23, 17, 45, 21, 6, 14, 56, 50};
	int n = 8;
	//构造了一个带头结点的单链表，注意带头结点
	createList(head, R, n);
	cout << "排序前" << endl;
	printList(head);
	quickSort(head->next, NULL);
	cout << "排序后" << endl;
	printList(head);
	
	
	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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90