待字闺中之快排(QuickSort)单向链表(Singly Linked List)

题目来源，待字闺中，原创@陈利人 ，欢迎大家继续关注微信公众账号“待字闺中”

分析：思路和数据的快速排序一样，都需要找到一个pivot元素、或者节点。然后将数组或者单向链表划分为两个部分，然后递归分别快排。

针对数组进行快排的时候，交换交换不同位置的数值，在分而治之完成之后，数据就是排序好的。那么单向链表是什么样的情况呢？除了交换节点值之外，是否有其他更好的方法呢？可以修改指针，不进行数值交换。这可以获取更高的效率。

在修改指针的过程中，会产生新的头指针以及尾指针，要记录下来。在partition之后，要将小于pivot的的部分、pivot、以及大于pivot的部分重新串起来成为一个singly linked list。

在partition时，我们用最后的节点作为pivot。当我们扫描链表时，如果节点值大于pivot，将节点移到尾部之后；如果节点小于，保持不变。

在递归排序时，我们先调用partition将pivot放到正确的为止并返回pivot，然后，递归左边，递归右边，最后在合成一个单链表。

具体代码如下：

#include <iostream>
#include <map>
#include <vector>
#include <assert.h>
using namespace std;

struct node
{
	int data;
	struct node* next;
	node(int x):data(x),next(NULL){}
};

node* partition(node* start,node* end,node** newHead,node** newEnd)
{
	node* provit = end,*tmp = NULL,*pre = NULL;
	while(start != provit)
	{
		if(start->data > provit->data)
		{
			tmp = start->next;
			if(pre)pre->next = tmp;
			start->next = NULL;
			end->next = start;
			end = start;
			start = tmp;
		}
		else
		{
			if(*newHead == NULL)*newHead = start;
			pre = start;
			start = start->next;
		}
	}
	if(*newHead == NULL)*newHead = provit;
	*newEnd = end;
	return provit;
}
node* GetTail(node* head)
{
	if(head == NULL)return NULL;
	while(head->next != NULL)head = head->next;
	return head;
}
node* QuickSort(node* head,node* end)
{
	if(head == NULL || head == end)return head;
	node* newHead = NULL,*newEnd = NULL;//此处不能用二维指针，不然partition调用*newHead解引用时会出错
	node* provit = partition(head,end,&newHead,&newEnd);
	if(newHead != provit)
	{
		node* tmp = newHead;
		while(tmp->next != provit)tmp = tmp->next;
		tmp -> next = NULL;
		newHead = QuickSort(newHead,tmp);
		tmp = GetTail(newHead);
		tmp->next = provit;
	}
	if(provit != newEnd)
	{
		provit->next= QuickSort(provit->next,newEnd);
	}
	return newHead;
}
void QuickSort(node** head)
{
	if(head == NULL)return;
	*head = QuickSort(*head,GetTail(*head));
}
void printLink(node* head)
{
	while(head != NULL)
	{
		cout << head->data <<" ";
		head = head->next;
	}
	cout << endl;
}
int main()
{
	int n,i,value;
	node* head,*q;
	cin >> n;
	for(i=0;i<n;i++)
	{
		cin >> value;
		if(i == 0)
		{
			head = new node(value);
			q = head;
		}
		else
		{
			node* p = new node(value);
			q->next = p;
			q = p;
		}
	}
	printLink(head);
	QuickSort(&head);
	printLink(head);
	return 0;
}

待字闺中之快排(QuickSort)单向链表(Singly Linked List),布布扣,bubuko.com

待字闺中之快排(QuickSort)单向链表(Singly Linked List)

原文：http://blog.csdn.net/fangjian1204/article/details/37760847