- #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);
- }
- //该片段来自于http://www.codesnippet.cn/detail/1501201614439.html
来源: http://www.codesnippet.cn/detail/1501201614439.html