[cpp] view plain copy print ?

typedef int ElemType;
typedef struct ListNode* List;
struct ListNode
{
ElemType key
List next;
};

typedef int ElemType;
typedef struct ListNode* List;

struct ListNode
{
	ElemType key
	List     next;
};

实现代码如下：

[cpp] view plain copy print ?

void QuickSort( List head, List tail )
{
if ( head->next == tail || head->next->next == tail )
return;
List mid = head->next;
List p = head;
List q = mid;
ElemType pivot = mid->key;
List t = mid->next;
while ( t != tail )
{
if ( t->key < pivot )
p = p->next = t;
else
q = q->next = t;
t = t->next;
}
p->next = mid;
q->next = tail;
QuickSort( head, mid );
QuickSort( mid, tail );
}

void QuickSort( List head, List tail )
{
	if ( head->next == tail || head->next->next == tail )
		return;

	List mid = head->next;
	List p = head;
	List q = mid;
	ElemType pivot = mid->key;
	List t = mid->next;
	
	while ( t != tail )
	{
		if ( t->key < pivot )
			p = p->next = t;
		else
			q = q->next = t;
		t = t->next;
	}
	p->next = mid;
	q->next = tail;

	QuickSort( head, mid );
	QuickSort( mid, tail );
}

调用时参数head为（带头节点的）单链表头节点指针，tail为单链表尾节点的next指针指向的类容。通常情况下tail的内容为NULL，因此，调用时为QuickSort(head, NULL)。

ITPub博客

算法单链表快速排序算法实现

最新文章