单链表简单选择排序算法

① 单链表的选择排序

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}*Linklist,Node;

Linklist creat(int n)
{
Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("输入数字:\n");
for(i=n;i>0;i--)
{
scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;
}
r->next=NULL;
return head;
}

void output(Linklist head)
{
Linklist p;
p=head->next;
do
{
printf("%8d",p->data);
p=p->next;
}while(p);
printf("\n");
}

void paixu(Linklist head)
{
Linklist p,q,small;
int temp;
for(p=head->next;p->next!=NULL;p=p->next)
{
small=p;
for(q=p->next;q;q=q->next)
if(q->data<small->data)
small=q;
if(small!=p)
{
temp=p->data;
p->data=small->data;
small->data=temp;
}
}
printf("输出排序后的数字:\n");
output(head);
}

void main()
{
Linklist head;
int n;
printf("输入数字的个数(n):\n");
scanf("%d",&n);
head=creat(n);
printf("输出数字:\n");
output(head);
paixu(head);
}

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

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<stdlib.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("输入数字:\n");
for(i=n;i>0;i--)
{scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;}
r->next=NULL;
return head;
} void output(Linklist head)
{Linklist p;
p=head->next;
do{
printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
} void paixu(Linklist head)
{Linklist p,q,small;int temp;

for(p=head->next;p->next!=NULL;p=p->next)
{small=p;
for(q=p->next;q;q=q->next)
if(q->data<small->data)
small=q;
if(small!=p)
{temp=p->data;
p->data=small->data;
small->data=temp;}
} printf("输出排序后的数字:\n");
output(head);
} void main()
{Linklist head;
int x,j,n;
printf("输入数字的个数(n):\n");
scanf("%d",&n);
head=creat(n);
printf("输出数字:\n");
output(head);
printf("已排序的数字:\n");
paixu(head);
}
第二种：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("输入数字:\n");
for(i=n;i>0;i--)
{scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;}
r->next=NULL;
return head;
} Linklist selectsort(Node *g)
{ Node *p,*q,*t,*s,*h;
h=(Node *)malloc(sizeof(Node));
h->next=g;
p=h;
while(p->next->next!=NULL)
{
for(s=p,q=p->next;q->next!=NULL;q=q->next)
if(q->next->data<s->next->data)
s=q;
if(s!=q)
{
t=s->next;
s->next=t->next;
t->next=p->next;
p->next=t;
}
p=p->next;
}
g=h->next;
free(h);
return g;
} void output(Linklist head)
{Linklist p;
p=head->next;
do{
printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
} void main()
{Linklist head;
int x,j,n;
printf("输入数字的个数(n):\n");
scanf("%d",&n);
head=creat(n);
printf("输出数字:\n");
output(head);
head=selectsort(head);
printf("已经排序的数字:\n");
output(head);
}

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

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;
}

⑤ 编写一个算法，用单链表表示的待排序关键码序列上实现简单选择排序。（用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;
}

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

⑥ 以单链表为存储结构，编写简单选择排序算法（需预先创建符合要求的单链表）

选择排序：从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

出这题的人是个坑货，链表交换很麻烦。
每次遍历找最小值时候 还要用一个指针定位到它前面一个， 才好交换。

⑦ 链表排序的算法

我看过了程序，觉得思想应该是这样的，9次遍历该链表。每次找出一个MAX，并将他赋给一个新的结点，同时删除原链表中这个最大值。
最后将这些新的接点组成一个链表，就是排好序的。
现在来看看程序中的错误，主要是在排序中：
⒈while条件错误，假如是temp!=NULL,想一想遍历到链表最一个值，这时temp不为NULL，而temp->next为NULL，while循环中用到了这个，所以程序崩溃。修改方法：该while条件，或是改循环中的temp->next。
⒉swaptemp->next=swaptemp->next->next;错误,会使程序崩溃，理由同上，应该是swaptemp->data=max;swaptemp=swaptemp->next;
⒊对max的处理应该放在while循环外面，这样才能对最大的max处理。
程序看上去比较得乱，也就没有调试，说了这么多你应该能自己调试成功吧。再说一下，尽量不要让程序有警告，有时警告也会让你的程序无法正常运行！

⑧ 单链表的简单排序

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

#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;
}

⑨ 设计一个用链表表示的直接选择排序算法，并用程序实现

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
typedef struct VNode
{
int info;
struct VNode *next_node;
}Node;
void input(Node*head, int number)
{
if(number!=0)
{
int i;
Node *t;
t=(Node *)malloc(sizeof(Node));
head->next_node=t;
scanf("%d",&i);
t->info=i;
input(t,number-1);
}
}
void output(Node*head, int count)
{
Node *t;
if(count!=0)
{
t=head->next_node;
printf("%d ",t->info);
output(t,count-1);
}
}
void select(Node*head, int num)
{
int tem=0;
if(num!=0)
{
int min_node;
Node *t;
Node *r;
Node *q;
t=head->next_node;
r= head->next_node;
q=head;
min_node= t->info;
for(int i=0;i<num;i++)
{
if(min_node>t->info)
{
min_node= t->info;
r=t;
tem=i;
}
t=t->next_node;
}
for(int j=0;j<tem;j++)
q=q->next_node;
q->next_node=r->next_node;
r->next_node=head->next_node;
head->next_node=r;
select(head->next_node,num-1);
}
}
int main()
{
int num;
Node *head;
head=( Node *)malloc(sizeof(Node));
printf("请输入序列数据的个数：");
scanf("%d",&num);
printf("请输入序列的数据：\n");
input(head,num);
printf("\n选择排序后的序列为：\n");
select(head,num);
output(head,num);
getch();}