数据结构的三种排序实验

川长思鸟来 2022-11-25 04:17 116阅读 0赞

## 数据结构的三种排序实验 ##

一、实验目的

1.  掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
2.  深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
3.  了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验内容：

1.  给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法并实现：按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；按名次输出每个学生的姓名与分数。
2.  各种排序方法的实现（要求至少实现三种排序方法）。

三、实验要求

1.两个题目都必做。  
2.在本题下面提交源程序和实验运行结果截图。  
3.上交纸质实验报告和电子版实验报告。  
4. 给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法并实现：按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；按名次输出每个学生的姓名与分数。

#include<stdio.h>
    #include<stdlib.h>
    #include<conio.h>
    #define n 3
    struct student {
        
        char name[8];
        int score;
    } R[n];
    main ( ) {
        
        int num, i, j, max;
        student temp;
        printf("\n请输入学生成绩: \n");
        for (i=0; i<n; i++) {
        
            printf ("姓名:");
            scanf ("%s", &(R[i].name));
            printf ("成绩:");
            scanf ("%d", &(R[i].score));
        }
        num=1;
        for (i=0; i<n; i++) {
        
            max=i;
            for (j=i+1; j<n; j++)
                if (R[j].score>R[max].score)
                    max=j;
            if (max!=i) {
        
                temp=R[max];
                R[max]=R[i];
                R[i]=temp;
            }
            if ((i>0)&&(R[i].score<R[i-1].score))
                num=num+1;
            printf("%4d\t%s%4d", num, R[i].name, R[i].score);
            printf("\n");
        }
        getch();
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]  
四、实验结果 8. 各种排序方法的实现（要求至少实现三种排序方法）。

1，冒泡排序

#include <stdio.h>
    int main(void)
    {
            
    int a[1001];    
    int n,i,j,t;
    printf("要排序的个数：");    
    scanf("%d",&n);//n为要排序的数的个数    //输入要排序的数    
    printf("输入排序数：");
    for(i=0;i<n;++i)        
    scanf("%d",a+i);
    printf("排序结果:\n");     //接下来进行排序    
    for(i=0;i<n-1;++i)//n个数,总共需要进行n-1次    
    {
                         //n-1个数排完,第一个数一定已经归位        //每次会将最大(升序)或最小(降序)放到最后面        
    for(j=0;j<n-i-1;++j)        
    {
                    
    if(a[j]>a[j+1])//每次冒泡,进行交换            
    {
                        
    t=a[j];                
    a[j]=a[j+1];                
    a[j+1]=t;            
    }        
    }        
    for(j=0;j<n;++j)            
    printf("%-5d ",a[j]);        
    printf("\n\n");    
    }     
    return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]

2，选择排序

#include <stdio.h>
    int main(void)
    {
        
        int a[1001];
        int n,i,j,t;
        printf("要排序的个数："); 
        scanf("%d",&n);//n为要排序的数的个数
        //输入需要排序的数
        printf("输入排序数：");
        for(i=0;i<n;++i)
            scanf("%d",a+i);
            printf("排序结果:\n");
        //接下来进行排序
        for(i=0;i<n-1;++i)
    	//因为每次需要和a[i]后面的数进行比较,所以到a[n-2](倒数第2个元素)就行
        {
        
            for(j=i+1;j<n;++j)//j从i后一个开始,a[i]与a[j]进行比较
            {
        
                if(a[i]>a[j])//a[i]为当前值,若是比后面的a[j]大,进行交换
                {
        
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            }//每排序一次,就会将a[i](包括a[i])之后的最小值放在a[i]的位置
            for(j=0;j<n;++j)
                printf("%-5d",a[j]);
            printf("\n\n");
        }
        return 0;
    }

3，插入排序

#include <stdio.h>
    int main(void)
    {
        
        int a[1001];
        int i,j,t,n;
        printf("要排序的个数："); 
        scanf("%d",&n);//输入要排序的数的个数
        printf("输入排序数：");
        for(i=0;i<n;++i)//输入要排序的数
            scanf("%d",a+i);
            printf("排序结果:\n");
        for(i=1;i<n;++i)
        {
        
            t=a[i];//将a[i]“拿在手中”
            for(j=i-1;j>-1 && a[j]>t;j--)//和前面的牌比
            {
        
                //如果前面的"牌"比手中的"牌"大,则将"牌"向后移
                a[j+1]=a[j];
            }//跳出循环则表明了"手中的牌的位置找到了"
            a[j+1]=t;//将"牌"插入
            for(j=0;j<n;++j)
                printf("%-5d",a[j]);
            printf("\n\n");
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]: /images/20221124/f2115cdc79d2407591baa0d266a8cf46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]: /images/20221124/b71312d2b65748019fd9936935716bc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 2]: /images/20221124/e8d33f9169e848eeb119c04facb2c632.png