单链表实现简单选择排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了单链表实现简单选择排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法思想：顺序遍历单链表，每当访问一个结点时，查看此结点往后的结点是否有更小的值，如果有更小值的结点，则交换两个结点元素的值(无需改变指针的指向)。每遍历一个结点就执行上诉操作，直到遍历到最后一个结点。

核心代码：

//以L指向的结点为起点，获取L之后最小元素的指针
linklist  getmin(linklist L){
	linknode *min;
	min=L;
	while(L->next){
		if(min->data>L->next->data){
			min=L->next;
		}
		L=L->next;
	}
	return min;
}

//简单选择排序，不改变指针的指向，通过交换元素的值实现。
void  choosesort(linklist head){
	linknode *p,*q;
	p=head->next;
	int temp;
	for(;p->next!=NULL;p=p->next){
		q=getmin(p);//获取p之后最小元素的指针
		if(q!=p){//如果有比p更小的元素，则交换两个结点的值
		    temp=p->data;
		    p->data=q->data;
		    q->data=temp;
		}
	}	
}

完整代码：

#include<stdio.h>
typedef  struct linknode{
	int data;
	struct linknode *next;
}linknode,*linklist;

linklist  initlist(linklist head){
	head=(linknode*)malloc(sizeof(linknode));
	if(head==NULL)
	return -1;
	head->next=NULL;
	return head;
}
 //尾插法创建单链表
void  rearinsert(linklist  head){
	linknode *rear,*s;
	int x;
	rear=head;//初始化头指针和尾指针
	scanf("%d",&x);
	while(x!=999){//输入要创建结点的值，当输入999时，退出while循环，创建单链表结束
		s=(linknode*)malloc(sizeof(linknode));//创建新结点
		s->data=x;
		rear->next=s;
		rear=s;//使rear指针始终指向最后一个结点
		scanf("%d",&x);
	}
	rear->next=NULL;
}

void  printlist(linklist  head){
	linknode *p=head;
	int j=0;
	while(p->next!=NULL){
	  p=p->next;
	  printf("%d  ",p->data);
	}
}

//以L指向的结点为起点，获取L之后最小元素的指针
linklist  getmin(linklist L){
	linknode *min;
	min=L;
	while(L->next){
		if(min->data>L->next->data){
			min=L->next;
		}
		L=L->next;
	}
	return min;
}

//简单选择排序，不改变指针的指向，通过交换元素的值实现。
void  choosesort(linklist head){
	linknode *p,*q;
	p=head->next;
	int temp;
	for(;p->next!=NULL;p=p->next){
		q=getmin(p);//获取p之后最小元素的指针
		if(q!=p){//如果有比p更小的元素，则交换两个结点的值
		    temp=p->data;
		    p->data=q->data;
		    q->data=temp;
		}
	}	
}
int  main(){
	linklist head;
	initlist(&head);
	rearinsert(&head);
	choosesort(&head);
	printlist(&head);
	
}

程序运行结果：

单链表实现简单选择排序