单链表快速排序和数组的快速排序差不多。选一个枢轴然后进行一次划分把数字交换到枢轴的两边。
这个过程需要交换，链表的交换就有两种方法，一个是交换节点，一个是直接交换节点的val值。交换val值比较方便。
写快排，一般都是递归。
数组版本的代码如下。
void quickSort(int a[], int low, int high)
{
if(low < high) //递归终止条件
{
//划分操作
int pivotpos = Partition(a,low,high);
quickSort(a, low, pivotpos-1);//对两个子序列排序
quickSort(a, pivotpos+1,high);
}
}
把这个改成递归的版本。
- 输入参数改一下， 链表给头和尾就行了。最开始的链表，我们不知道真正的链表尾巴是哪个节点，但是知道最后一个节点的
next一定是NULL，所以这里输入的链表的范围是相当于从start节点开始到next为end的节点结束。所以：void quickSort(LinkList start, LinkList end)第一次调用的时候end为NULL。 - 递归终止条件改一下。
start->next != end && start != end所以终止的条件就是start->next == end || start == end，看第一个条件start->next == end就说明start链表里只有一个start这一个节点。这种情况就不需要排了。第二个条件start == end就是这个链表里一个节点没有，那也就不用排了。 -
partition函数，数组版本返回的是枢轴位置的下标，链表版本就应该返回指向枢轴节点的指针。 - 接下来就是递归调用。前半段的
start还是start,end变成了mid(枢轴的节点，因为这里的end是待排序的链表最后一个节点的next)。后半段的start自然就是mid->next,end还是原来的数组的end。
//链表
void quickSort(LinkList start, LinkList end)
{
if(start->next != end && start != end)
{
Node * mid = partition(start, end);
quickSort(start, mid);
quickSort(mid->next, end);
}
}
接下来看看关键的划分是怎么办。
该贴出来数据结构课本上这图了。
image.png
有两个游标，一个从前往后走，一个从后往前走，两个碰到的位置就是枢轴的最终位置，一趟划分结束。
单项链表就没有游标从后往前走这种操作了，所以有这么一种方法。
选第一个数当枢轴，一个指针p记录比枢轴小的最后一个数，另一个指针q进行遍历，如果比枢轴大就继续便利，如果发现比枢轴小的值往前换（p先往后挪一下再换，防止把小数换后头去）遍历到最后，把第一个位置的值和p位置的值换一个下，p这时候使比枢轴小的数的最后一个，和第一个的枢轴换一下正好枢轴归位并且用一个比枢轴小的数把第一个位置填上了。
Node * partition(LinkList start, LinkList end)
{
Node *p = start;
Node *q = p->next;
printList(start, end);
int pivot = start -> val;
cout << "↑pivot: " << pivot << endl;
while(q!= end)
{
if(q->val < pivot)
{
p = p->next;
swap(p->val, q->val);
}
q=q->next;
}
swap(p->val,start->val);
return p;
}
举个栗子
遍历时候两种情况：
- q->val < pivot ： {p = p->next; swap(p->val, q->val); q = q->next; }
- 另一种情况： { q = q->next; }
枢轴等于 4
4 2 5 3 7 9 0 5
↑ ↑
p q
（2比4小， p++ , 换，q++ ，2换2 ）
4 2 5 3 7 9 0 5
↑ ↑
p q
（5比4大， q++ ）
4 2 5 3 7 9 0 5
↑ ↑
p q
（3比4小， p++ , 换，q++ ，5换3 ）
4 2 3 5 7 9 0 5
↑ ↑
p q
（7比4大， q++ ）
4 2 3 5 7 9 0 5
↑ ↑
p q
（9比4大， q++ ）
4 2 3 0 7 9 5 5
↑ ↑
p q
（0比4小， p++ , 换，q++ ，0换5 ）
4 2 3 0 7 9 5 5 NULL
↑ ↑
p q
（5比4大， q++，便利完，结束 ）
（然后把p和枢轴换 4换0）
0 2 3 4 7 9 5 5 NULL
↑ ↑
p q
（p就是枢轴位置，返回p）
程序截图。。。
完整代码：
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
} Node, *LinkList;
void printList(LinkList l)
{
int sum = 0;
while(l != NULL)
{
cout << l->val <<" ";
sum += l->val;
l = l->next;
}
cout << " sum = "<< sum;
cout << endl;
}
void printList(LinkList s, LinkList e)
{
while(s!= e)
{
cout << s->val<< " ";
s = s->next;
}
cout << endl;
}
LinkList creatList(int *data, int n)
{
LinkList head = new Node(0);
LinkList tail = head;
for(int i = 0; i < n; i++)
{
LinkList n = new Node(0);
n->val = data[i];
tail->next = n;
tail = tail->next;
}
printList(head->next, NULL);
LinkList r = head->next;
delete(head);
return r;
}
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
Node * partition(LinkList start, LinkList end)
{
Node *p = start;
Node *q = p->next;
printList(start, end);
int pivot = start -> val;
cout << "↑pivot: " << pivot << endl;
while(q!= end)
{
if(q->val < pivot)
{
p = p->next;
swap(p->val, q->val);
}
q=q->next;
}
swap(p->val,start->val);
return p;
}
void quickSort(LinkList start, LinkList end)
{
if(start->next != end && start != end)
{
Node * mid = partition(start, end);
cout << "划分之后： "<< endl;
printList(start, end);
quickSort(start, mid);
quickSort(mid->next, end);
}
}
int main()
{
//int n = 19;
//int array[n];
/*for(int i = 0; i < n; i++)
{
int t = rand()%n;
array[i] = t;
}*/
int n = 8;
int array[] = {4, 2, 5, 3, 7, 9, 0, 5};
LinkList l = creatList(array, n);
quickSort(l, NULL);
printList(l, NULL);
}
网友评论