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

typedef struct{
	char name[20];
	int score;
}ElemType;

typedef struct{
	ElemType *elem;
	int length;
}SqList;

void menu();

void SlectSort(SqList L);
void InsertSort(SqList ST);
int partition(SqList &L,int low,int high);
void Qsort(SqList &L,int low,int high);

int main()
{
	printf("\n******学生成绩排序******");
	printf("\n\n**************************\n");
	printf("  1  -------  输入学生数\n");
	printf("  2  -------  输入学生姓名及成绩\n");
	printf("  3  -------  用直接插入排序输出名次\n");
	printf("  4  -------  用快速排序输出名次\n");
	printf("  5  -------  用选择排序输出名次\n");
    printf("  6  -------  退出\n");
	printf("  请选择1-6\n");
	printf("**************************\n");
	menu();
	return 0;

}
void menu()
{
	SqList ST;
	int key,n,i,done=1;
	while (done) 
	{
		printf("请输入数字 : ");
		scanf("%d",&key);
		switch(key)
		{
		case 1:
			printf("请输入学生数：（n>=10）");
			scanf("%d",&n);
			break;
        case 2:
			ST.length=n;
			ST.elem=(ElemType*)malloc((n+1)*sizeof(ElemType));
			for(i=1;i<=n;i++)
			{
				printf("请输入第%d个学生的基本信息：（姓名 成绩）\n",i);
				scanf("%s%d",ST.elem[i].name,&ST.elem[i].score);
			}
			break;
		case 3:
                 //直接插入排序
			InsertSort(ST);
			break;
                case 4:
                 //快速排序
			Qsort(ST,1,ST.length);
			for(i=1;i<=ST.length;i++)
				printf("第%d名:%s  %d\n",i,ST.elem[i].name,ST.elem[i].score);
			break;
		case 5:
                 //选择排序
			SlectSort(ST);
			break;
		case 6:
			done=0;
			break;
        default: printf(" ERROR\n");     
		}
		printf("\n");
	}
}
void InsertSort(SqList ST)
{
	int i,j;
	for(i=2;i<=ST.length;++i)
		if(ST.elem[i].score>ST.elem[i-1].score)
		{
			ST.elem[0]=ST.elem[i];
			ST.elem[i]=ST.elem[i-1];
			for(j=i-2;ST.elem[0].score>ST.elem[j].score;--j)
				ST.elem[j+1]=ST.elem[j];
			ST.elem[j+1]=ST.elem[0];
		}
	for(i=1;i<=ST.length;i++)
		printf("第%d名:%s  %d\n",i,ST.elem[i].name,ST.elem[i].score);
}
int partition(SqList &L,int low,int high)
{
	int pivotkey;
	pivotkey=L.elem[low].score;
	L.elem[0]=L.elem[low];
	while(low<high)
	{
		while(low<high&&L.elem[high].score<=pivotkey)
			--high;
		L.elem[low]=L.elem[high];
		while(low<high&&L.elem[low].score>=pivotkey)
			++low;
		L.elem[high]=L.elem[low];
	}
	L.elem[low]=L.elem[0];
	return low;
}
void Qsort(SqList &L,int low,int high)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=partition(L,low,high);
		Qsort(L,low,pivotloc-1);
		Qsort(L,pivotloc+1,high);
	}
}
void SlectSort(SqList L)
{
	int i,j,k;
	ElemType temp;
	for(i=1;i<L.length;i++)
	{
		k=i;
		for(j=i+1;j<=L.length;j++)
			if(L.elem[j].score>L.elem[k].score)
				k=j;
		if(i!=k)
		{
			temp=L.elem[k];
            L.elem[k]=L.elem[i];
			L.elem[i]=temp;
		}
	}
	for(i=1;i<=L.length;i++)
		printf("第%d名:%s  %d\n",i,L.elem[i].name,L.elem[i].score);
}