带头结点的单链表按数据域从小到大进行选择排序的算法

选择排序的每一趟原理是从当前未排好序的元素中，选择一个值最小的元素，将其与未排号的那些元素的第一个元素进行交换位置。按照这个原理，请写一个带头结点的单链表按数据域从小到大进行选择排序。

限制：排序过程中不得申请如何链结点空间，也不能改变任何链结点的数据域内容。

思想：按照简单排序从当前未排好序的元素中，选择一个值最小的元素，将其与未排号的那些元素的第一个元素进行交换位置进行。

例子1：[1，3，4，2，5]

head=1->3->4->2->5

开始时，p=3,q=1,min=p=3,minpre=q=1;s=4,spre=3。

找到最小值min=2，此时minpre=4，minnext=5。

则，q->next=2，p和min之间还有元素，min->next=p->next=4；minpre->next=p=3；p->next=minnext=5; 

最后链表为：head=1->2->4->3->5

例2：

[1，3，2，5]

head=1->3->2->5

开始时，p=3,q=1,min=p=3,minpre=q=1;s=2,spre=3。

找到最小值min=2，此时minpre=3，minnext=5。

则，q->next=2，p和min之间没有元素，p->next=minnext=5；min->next=p=3;

最后链表为：head=1->2->3->5

代码：

void selectsort(LinkList head){
	LNode *p=head->next;//无序部分的头结点
	LNode *q=head;//有序部分的最后一个结点，也是无序部分的前驱
	
	//无序部分有2个以上结点时。
	while(p->next != NULL){
		LNode *min=p;//初始化无序部分第一个元素是最小值
		LNode *minpre=q;//初始化最小元素的前驱
		LNode *s=p->next;//移动指针，在无序部分找是否有比无序第一个元素更小的元素 
		LNode *spre=p;//初始化移动指针的前驱
		
		
		while(s!=NULL){
			//出现更小的值 
			if(s->data<min->data){
				minpre=spre;
				min=s;
			}
			//往后遍历 
			spre=s;
			s=s->next;
		} 
		
		//将最小的值与无序部分第一个元素进行交换 
		
		if(min != p){
			LNode minnext=min->next;//最小值结点的后继
			
			//将最小结点放到无序部分的头部
			q->next=min;
			//p为最小元素的直接前驱时 
			if(p->next=min) {
				p->next=minnext;
				min->next=p;
			}esle{//p和min之间还有元素时 
				min->next=p->next;
				minpre->next=p;
				p->next=minnext; 
			}
		}
		q=q->next;//有序部分增加一个结点 
		p=q->next;//无序部分减少一个结点 
	} 
}