c++ 单链表排序及测试案例

c++ 单链表排序及测试案例

#include
using namespace std;

//链表结构体
typedef struct Node
{
	int val;
	struct Node* next;
}linkNode;

//寻找支点
Node* GetPoint(linkNode* head, linkNode* tail)
{
	int key = head->val;  //假设支点的值为头节点的值
	linkNode* p = head;   //定义一个指针指向头结点
	linkNode* q = head->next; //定义一个指针指向头结点的下一个节点

	while (q != tail)//循环条件，头结点的下一个节点不是尾节点也就是NULL
	{
		if (q->val < key) //区分支点左右值，一般支点左边值小于支点值，右边大于支点值
		{
			p = p->next;   //优先执行让当前节点指针等于当前节点指针的下 一个节点，保证假设支点的值在寻找到支点位置的时候是不能修改的
			swap(p->val, q->val);	
		}
		q = q->next;
	}
	//把假设的支点的值和寻找到支点位置所在的值交换
	//支点的值和位置绑定
	swap(head->val, p->val);
	return  p; //返回支点值所在的节点指针
}

void quickSock(linkNode* head, linkNode* tail)
{
	if (head != tail)
	{
		Node* pp = GetPoint(head, tail);
		quickSock(head, pp);
		quickSock(pp->next, NULL);
	}
	
}

int main()
{

	linkNode *n1=new linkNode();
	n1->val = 4;

	linkNode* n2 = new linkNode();
	n2->val = 2;

	linkNode* n3 = new linkNode();
	n3->val = 3;

	linkNode* n4 = new linkNode();
	n4->val = 0;

	linkNode* n5 = new linkNode();
	n5->val = 1;

	linkNode* n6 = new linkNode();
	n6->val = 9;

	linkNode* n7 = new linkNode();
	n7->val = 5;

	linkNode* n8 = new linkNode();
	n8->val = 7;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	n7->next = n8;
	n8->next = NULL;

	
	cout <<"***********************"<< endl;
	quickSock(n1, NULL);

	while (n1 != NULL)
	{
		cout << n1->val<< " ";
		n1 = n1->next;
	}
	cout << endl;

	return  0;
}