实验八、排序算法的实现

一、实验目的

1. 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；
2. 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；
3. 了解各种方法的排序过程及其时间复杂度的分析方法。
   二、实验要求
   统计成绩：给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：
   （1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；
   （2） 按名次列出每个学生的姓名与分数。
   三、实验步骤
   1.定义结构体。
   Typedef struct student
   { char name[8];
   int score; }
   2.定义结构体数组。
   3.编写主程序，对数据进行排序。
   4.要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。
   4.1直接插入排序基本思想
   排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。
   

4.2 快速排序基本思想
基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。
排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设rp=r[s]，x=rp.key。初始时令i=s,j=t。首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i=j为止。再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。

四、实验任务
认真阅读与理解实验内容的具体要求，参考教材相关章节，编写实验程序并上机调试与测试，完成实验报告的撰写。

代码如下

#include<stdio.h>
#include<stdlib.h>
typedef  struct
{
    char  name[10];
    int  score;
} student;
//=========================================
void InsertSort(student a[],int n)//冒泡排序算法
{
    int i,j,flag;
    student temp;
    for(i=0; i<n-1; i++)
    {
        flag=0;
        for(j=0; j<n-i-1; j++)
        {
            if(a[j].score<a[j+1].score)
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                flag=1;
            }
        }
        if(flag==0)  break;
    }
}
//=============================
void SelectionSort(student a[],int n)//简单选择排序
{
    int i,j,k;
    student temp;
    for(i=0; i<n; i++)
    {
        k=i;
        for(j=i; j<n; j++)
        {
            if(a[j].score>a[k].score)  k=j;
        }
        if(k!=i)
        {
            temp=a[i];
            a[i]=a[k];
            a[k]=temp;
        }
    }
}
int main()
{
    int n,i,k,t;
    student *a;
    printf("您要输入多少个学生的信息？\n");
    scanf("%d",&n);
    a=(student *)malloc(n*sizeof(student));
    printf("请输入学生姓名和成绩：\n");
    for(i=0; i<n; i++)
    {
        scanf("%s %d",&a[i].name,&a[i].score);
    }
    printf("您想使用哪种排序算法？(1)使用冒泡排序,(2)使用简单选择排序\n");
    scanf("%d",&k);
    if(k==1)
    {
        InsertSort(a,n);
    }
    else if(k==2)
    {
        SelectionSort(a,n);
    }
    printf("第%d名:   %s   %d\n",1,a[0].name,a[0].score);
    t=1;
    for(i=1; i<n; i++)
    {
        if(a[i].score==a[i-1].score)
        {
            printf("第%d名:   %s   %d\n",t,a[i].name,a[i].score);
        }
        else
        {
            t=i+1;
            printf("第%d名:   %s   %d\n",t,a[i].name,a[i].score);
        }
    }
    free(a);
    return 0;
}