单链表实现选择排序算法

㈠ 对单链表中的数据进行排序，用哪种算法比较好

typedef struct __LINK
{
int data;
struct __LINK *next;
} LinkNode_t;

//冒泡排序单连表, 交换值方式
bool LinkSort( LinkNode_t* &head )
{
assert( head != NULL );
bool change = true;
LinkNode_t* p = head;
LinkNode_t* pStop = head->next;
int ifirst = 0;

while ( pStop && pStop->next )
{
pStop = pStop->next;
}

LinkNode_t* pFlag = head;

while ( change )
{
change = false;
for ( p = head->next; p != pStop; p = p->next )
{
if ( p->data < p->next->data )
{
int value = p->data;
p->data = p->next->data;
p->next->data = value;
change = true;
}
if ( p->next == pStop ) pFlag = p;
}
pStop = pFlag;
}
return true;
}

㈡ 单链表的简单排序

最简单的选择排序具体看代码：

#include<cstdio>
#include<cstdlib>
#include<ctime>
structnode{
intval;
node*next;
node(intv):val(v),next(NULL){}
};
//从小到大，最简单的选择排序
node*linklist_sort(node*head){
node*nhead=newnode(0);
while(true){
node*temp=head,*maxpre=head;
for(;temp->next;temp=temp->next){
if(temp->next->val>maxpre->next->val){
maxpre=temp;
}
}
if(temp==head)break;
temp=maxpre->next;
maxpre->next=temp->next;
temp->next=nhead->next;
nhead->next=temp;
}
head->next=nhead->next;
returnhead;
}
voidtraval(node*head){//遍历单链表
while(head->next){
printf("%d",head->next->val);
head=head->next;
}
printf("
");
}
intmain(){
srand(time(NULL));
node*head=newnode(0);
for(inti=0;i<10;i++){
node*t=newnode(rand()%1000);
t->next=head->next;
head->next=t;
}
traval(head);
head=linklist_sort(head);
traval(head);
return0;
}

㈢ 若待排序列用带头结点的单链表存储,试给出简单选择排序算法. 求大神！

voidselectsort(pointer&h)//h为头指针
{
	pointerpCur=h;
	pointerpCurPre=NULL;
	pointerpMin=pCur;
	pointerpMinPre=pCurPre;
	boolbFirstFlag=true;

	while(pCur)
	{
		//遍历以pCur为头节点的链表中key值最小的节点
		pMin=pCur;
		pMinPre=pCurPre;
		pointerpTemp1=pCur;
		while(pTemp1->next)
		{
			if(pMin->key>pTemp1->next->key)
			{
				pMin=pTemp1->next;
				pMinPre=pTemp1;
			}

			pTemp1=pTemp1->next;
		}

		//交换key值最小的节点与pCur节点的位置
		if(pCur->next==pMin)
		{
			pCur->next=pMin->next;
			pMin->next=pCur;
			pCurPre->next=pMin;
		}
		else
		{
			pointerpTemp2=pCur->next;
			pCur->next=pMin->next;
			pMin->next=pTemp2;

			if(pCurPre)
			{
				pCurPre->next=pMin;
			}

			if(pMinPre)
			{
				pMinPre->next=pCur;
			}
		}

		if(bFirstFlag)
		{
			h=pMin;
			bFirstFlag=false;
		}

		pCurPre=pMin;
		pCur=pMin->next;
	}
}

㈣ 编写一个算法，用单链表表示的待排序关键码序列上实现简单选择排序。（用c写）

#include"stdio.h"
#include<malloc.h>

typedef char ElemType;

typedef struct LNode
{ElemType data;
struct LNode *next;
}LinkList;

void CreateListR(LinkList *&L,ElemType a[],int n) //尾插法建表
{
LinkList *s,*r;int i;
L=(LinkList *)malloc(sizeof(LinkList));
r=L;
for(i=0;i<n;i++)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}

void InitList(LinkList *&L) //初始化线性表
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}

void DispList(LinkList *L) //输出线性表
{
LinkList *p=L->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
}

void CombList(LinkList *L1,LinkList *L2,LinkList *&k) //两个集合的交
{
LinkList *p=L1->next ,*q=L2->next ,*b,*a,*c;

k=(LinkList *)malloc(sizeof(LinkList));
b=k;a=p;
while(q!=NULL)
{
while(a!=NULL)
{
if(a->data==q->data)
{
c=(LinkList *)malloc(sizeof(LinkList));
c->data=a->data;b->next=c;b=b->next;
}
a=a->next;
}
q=q->next;
a=p;
}
b->next=NULL;
}

void AddList(LinkList *L1,LinkList *L2,LinkList *&k) //两个集合的并
{
LinkList *p=L1->next ,*q=L2->next ,*b,*a,*c;

k=(LinkList *)malloc(sizeof(LinkList));
b=k;a=p;

while(q!=NULL)
{
int x=0;
while(p!=NULL)
{
if(p->data==q->data)x++;
p=p->next;
}
if(!x)
{
c=(LinkList *)malloc(sizeof(LinkList));
c->data=q->data;b->next=c;b=b->next;
}
q=q->next;
p=a;
}
b->next=a;
}

void RankList(LinkList *&L) //按从小到大排列
{
LinkList *p=L->next,*q,*r;
if (p!=NULL)
{ r=p->next;
p->next=NULL;
p=r;
while (p!=NULL)
{ r=p->next;
q=L;
while (q->next!=NULL && q->next->data<p->data)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
}
int main()
{
ElemType a[5]={'a','b','c','d','e'},b[4]={'e','f','g','h'};
LinkList *h1,*h2,*p1,*p2;

InitList(h1); //初始化顺序表h
InitList(h2);
CreateListR(h1,&a[0],5); //依次采用尾插入法插入a，b，c，d，e元素
CreateListR(h2,&b[0],4);
printf("单链表1为：");
DispList(h1); printf("\n"); //输出顺序表h
printf("单链表2为：");
DispList(h2); printf("\n");

CombList(h1,h2,p1); //求两个单链表的交
printf("这两个单链表的交为：");
DispList(p1); printf("\n");

AddList(h1,h2,p2); //求两个单链表的并
printf("这两个单链表的并为：");
DispList(p2); printf("\n");

RankList(p2); //对单链表按从小到大排列
printf("这个单链表排列后为：");
DispList(p2); printf("\n");

return 0;
}

这个是我以前做的作业，你可拿去借鉴一下，其实程序这东西还是要自己多看多写，自然就会不断进步，如果只是拿别人的而不自己去思考很难有进步哦。
祝你能学习进步。