单链表冒泡排序(交换节点法、移动指针法)

单链表的排序算法(待续)

//带头结点的单链表排序
void LinkSort(LinkList *L)
{
	LinkNode temp;
	LinkList pf = (*L)->next;//第一个有数据的节点
	LinkList pb;
	if(pf == NULL)
	{
		printf("空链表，无需排序\n");
	}
	else if(pf->next == NULL)
	{
		printf("只有一个元素，无需排序:\n");
	}
	else
	{
		while(pf != NULL)
		{
			pb = pf->next;//pb每次初始化为pf的下一个节点
			while(pb != NULL)
			{
				if(pf->sum > pb->sum)
				{
					//先把结构体内容交换
					temp = *pb;
					*pb = *pf;
					*pf = temp;
					//再把两个结构体中的next域交换回来
					temp.next = pf->next;
					pf->next = pb->next;
					pb->next = temp.next;
				}
				pb = pb->next;//pb向后移动
			}
			pf = pf->next;
		}
	}
}
//有点像冒泡排序，也有点像选择排序

//正宗冒泡
void LinkSort(LinkList *L)
{
	LinkList tail = NULL;
	int change = 1;//判断是否可以结束冒泡
	while(tail != (*L)->next && change == 1)
	{
		LinkList pre = *L;//比较的第一个的前一个
		LinkList pf = (*L)->next;//比较的第一个
		LinkList ps = pf->next;//比较的第二个
		change = 0;//若不在设置为1，则结束排序
		while(pf != tail && pf->next != tail)
		{
			if(pf->sum > ps->sum)
			{
				change = 1;//若交换了，指示器设为1，下次继续排序
				pre->next = ps;
				pf->next = ps->next;
				ps->next = pf;
			}
			pre = pre->next;
			pf = pre->next;
			ps = pf->next;
		}
		tail = pf;
	}
}