返回顶部

收藏

直接插入排序,快速排序,选择排序给学生成绩排名

更多
#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 &amp;L,int low,int high);
void Qsort(SqList &amp;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",&amp;key);
        switch(key)
        {
        case 1:
            printf("请输入学生数:(n>=10)");
            scanf("%d",&amp;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,&amp;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 &amp;L,int low,int high)
{
    int pivotkey;
    pivotkey=L.elem[low].score;
    L.elem[0]=L.elem[low];
    while(low<high)
    {
        while(low<high&amp;&amp;L.elem[high].score<=pivotkey)
            --high;
        L.elem[low]=L.elem[high];
        while(low<high&amp;&amp;L.elem[low].score>=pivotkey)
            ++low;
        L.elem[high]=L.elem[low];
    }
    L.elem[low]=L.elem[0];
    return low;
}
void Qsort(SqList &amp;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);
}

标签:lua

收藏

0人收藏

支持

0

反对

0

发表评论