数据结构 排序（冒泡排序改进，简单选择排序链表实现）

实验题目：     排序算法实现与比较            

实验环境：    Visual C++ 6.0                   　

实验八：

实验目的和要求：熟悉多种排序算法，理解每种排序算法思想，掌握排序算法的基本设计方法，掌握排序算法时间复杂度和空间复杂度的分析方法。

实验内容：1.对所讲过算法深入理解。

          2. 将冒泡排序再做进一步的优化。如果有100个数的数组，当前仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在该一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，下次只要从数组头部遍历到这个位置就可以了。

           3. 试以单链表为存储结构，实现简单选择排序算法。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define MAXSIZE 20
using namespace  std;
typedef struct
{
    int key;
    char *otherinfor;
}ElemType;
typedef struct
{
	ElemType *r;
	int length;
}SqList;
void BubbleSort(SqList &L)//冒泡排序 
{
	int c,i,m=L.length;
	ElemType t;
	while(m>0)
	{
		for(c=0,i=1;i<m;i++)
		{
			if(L.r[i].key>L.r[i+1].key)
			{
				t=L.r[i];
				L.r[i]=L.r[i+1];
				L.r[i+1]=t;
				c=i;
			}
		} 
		m=c;
	}
}
void CreatSqList(SqList &L)
{
	int i,n;
	printf("请输入数据个数(<MAXSIZE)\n");
	scanf("%d",&n);
	printf("请输入待排序的序列\n");
	for(i=1;i<=n;i++)
	{
		scanf("%d",&L.r[i].key);
		L.length++; 
	}
}
void ShowSqList(SqList L)
{
	int i;
	for(i=1;i<=L.length;i++)
	{
		cout<<L.r[i].key<<endl;
	}
	printf("\n");
}
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode, *LinkList;
void InitList(LinkList &L)
{
	L=(LNode*)malloc(sizeof(LNode));
	L->next=NULL;
}
void IntPut(LinkList &L,int m)
{
	int i;
	LinkList r,p;
	r=L;
	for(i=0;i<m;i++)
	{
		p=(LNode*)malloc(sizeof(LNode));
		cin>>p->data;
		p->next=NULL;
		r->next=p;
		r=p;
	}
}
void OutPut(LinkList &L)
{
	LinkList p;
	p=(LNode*)malloc(sizeof(LNode));
	p=L->next;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next; 
	 } 
}
void SelectSort(LinkList &L)//简单选择排序 
{
	LinkList r,q,p=L->next;
	int t; 
	while(p)
	{
		q=p->next;
		r=p;
		while(q)
		{
			if(q->data<r->data)
			    r=q;	
			q=q->next;
		}
		if(r!=p)
		{
			t=r->data;
			r->data=p->data;
			p->data=t;
		}
		p=p->next;
	} 
}
int main()
{
	SqList L;
	LinkList Q;
	int m;
	L.r=(ElemType*)malloc(sizeof(ElemType));
	L.length=0;
	CreatSqList (L);
	BubbleSort(L);
	ShowSqList(L);
	printf("请输入需要排序的数的个数\n");
    scanf("%d",&m);
	InitList(Q);
    IntPut(Q,m);
    SelectSort(Q);
    OutPut(Q);
}