山东大学数据结构与算法分析: 实验4 排序的编程与实现

一、实验目的

掌握常用的排序方法，并掌握C语言实现排序算法的方法；了解各种排序方法过程及依据原则，并掌握各种排序方法的时间复杂度和稳定性的分析方法。

二、实验原理

参照课本p.220, Figure7.2；p.223，Figure7.4;p.228,Figure7.8;p.232-233, Figure7.9-7.10; p240-243, Figure 7.12-7.15.

三、实验内容

统计成绩

【问题描述】：给出n个学生的考试成绩表，每条信息由姓名和分数组成，利用排序算法完成以下任务：

1)按照分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次。

2)按照名次列出每个学生的姓名和分数

【要求】学生的考试成绩需要从键盘输入数据建立，同时要设计输出格式。

四、实验要求

1)能够采用常用的排序算法中的一种实现以上两个任务；

五、实验源程序

#include "stdio.h"
#include "string"
#include "string.h"

using std::string;

int main(){
    string name[100];
    int score[100];
    int rank[100];
    int number;
    printf("请输入学生人数：\n");
    scanf("%d",&number);
    printf("请输入姓名和分数(用空格分开)：\n");
    for(int i=0;i<number;i++)
    {
        scanf("%s %d",&name[i],&score[i]);
        rank[i]=i;
    }
    int min;
    int tmp;
    int i;
    for(i=0;i<number;i++){
        for(int j=i+1;j<number;j++)
        {
            if(score[i]<score[j])
            {
                min=score[i];
                score[i]=score[j];
                score[j]=min;
                
                tmp=rank[i];
                rank[i]=rank[j];
                rank[j]=tmp;
            }
        }
    }
    printf("\n排序后：\n");
    printf("姓名        分数        排名\n");
    int n=1;
    for(i=0;i<number;i++)
    {
        int m=rank[i];
        printf("%s         %d",&name[m],score[i]);
        printf("           %d\n",n);
        if(score[i]==score[i+1])
        {
            n--;
        }
        n++;
    }
    return 0;
}