数据结构实验六 排序算法的实现

★观前提示：本篇内容为数据结构实验，代码内容经测试没有问题，但是可能会不符合每个人实验的要求，因此以下内容建议仅做思路参考。

（1）掌握常见的交换排序算法的思想及适用条件；

（2）掌握常见的交换排序算法的程序实现。

（3）了解各种交换排序的排序过程及其时间复杂度的分析方法。

统计成绩： 给出 n 个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：

（1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；
（2） 按名次列出每个学生的姓名与分数。

★温馨提示：以下代码均为改正过的代码，皆已经过测试。

1、冒泡排序和选择排序

#include
#include	//定义头文件 
#include
//定义学生类结构体 
typedef  struct
{
    char  name[10];
    int  score;
} student;
//   ==冒泡排序==
void InsertSort(student a[],int n)
{
    int i,j,flag;
    student temp;
    for(i=0; i
        flag=0;
        for(j=0; j
            if(a[j].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
        k=i;
        for(j=i; 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;//定义四个整型变量 n,i,k,t 
    student *a; //定义结构体指针a 
    printf("请输入学生人数：n");
    scanf("%d",&n);
    a=(student *)malloc(n*sizeof(student));//动态申请内存空间 
    printf("请输入学生姓名和成绩：n");
    for(i=0; i
        scanf("%s %d",&a[i].name,&a[i].score);//借助for循环循环输入名字和成绩 
    }
    printf("请选择您要使用的排序算法:n(1)使用冒泡排序n(2)使用简单选择排序n");
    
    scanf("%d",&k);
    if(k==1)
        InsertSort(a,n);      //冒泡排序函数调用 
  
    else if(k==2)
    {
        SelectionSort(a,n);   //简单选择排序函数调用 
    }

    printf("第%d名:  %s  %dn",1,a[0].name,a[0].score);
    t=1;
    for(i=1; i
        if(a[i].score==a[i-1].score)        
            printf("第%d名:  %s  %dn",t,a[i].name,a[i].score);
        
        else{
            t=i+1;
            printf("第%d名:  %s  %dn",t,a[i].name,a[i].score);
        }
    }
    free(a);//释放掉所申请的空间 
    return 0;
}

2、快速排序

#include
#include	//定义头文件 
#include
#define MAXSIZE 101

//学生信息__结构体定义 
typedef struct
{
	char name[10];//姓名 
	int score;//成绩 
}Stu;

//顺序表__结构体定义 
typedef struct{
	Stu s[MAXSIZE]; //结构体类型数组 
	int length; //顺序表长度
}SqList;

//快速排序__插入操作	
void insertList(SqList &L)
{
	printf("请输入学生人数:n");
	int n;
	scanf("%d",&n);
	printf("请输入%d个学生n",n);
	for(int i=1;i<=n;i++)
	{
		printf("请输入第%d个学生的姓名和成绩n",i);
		scanf("%s",&L.s[i].name);
		scanf("%d",&L.s[i].score);
	}
	L.length=n;
	printf("%d个元素插入成功n",n);
}
	
//显示函数，显示姓名与成绩	
void Display(SqList L)
{
	for(int i=L.length;i>0;i--)
	{
		printf("第%d名 %s %dn",i,L.s[i].name,L.s[i].score); 
	}
	printf("n");
}

//快速排序算法__查找位置 
int FindPos(SqList &L,int low,int hight)
{
	int pivotkey;
	L.s[0]=L.s[low];
	pivotkey=L.s[low].score;
	while(low
	while(low=pivotkey)
	{
		hight=hight-1;
	}
	L.s[low]=L.s[hight];
	while(low
		low=low+1;
	}
	L.s[hight]=L.s[low];
	}
	L.s[low]=L.s[0];
	return low;
}

//快速排序算法的实质就是当前分为两半，分别给这两半进行快速排序，直到low==hight 的时候
void Qsort(SqList &L,int low,int hight)
{ 
	int pos;
	if(low
		pos=FindPos(L,low,hight); //先对整体进行一次快速排序，将其分成两半
		Qsort(L,low,pos-1); //然后分别对pos 位置左边的部分在进行快速排序，位置右边的部分进行快速排序
		Qsort(L,pos+1,hight);
	}
}

//快速排序 
void QuickSort(SqList &L)
{
	Qsort(L,1,L.length);
}

//主函数 
int main()
{
	printf("-----------快速排序-------------n");
	SqList L;
	insertList(L);
	printf("初始化后的SqList为:n");
	Display(L);
	QuickSort(L);
	printf("排序后为:n");
	Display(L);
	return 0;
}

① 通过本次实验，了解并掌握了一些常见交换排序算法的思想还有适用条件，对排序算法有了更深的认识和了解。
② 通过多次尝试对排序算法的代码实现，理解并掌握了冒泡排序、简单选择排序、快速排序的实现方法步骤。
③ 明白了冒泡排序、简单选择排序、快速排序的代码实现逻辑，了解了各种交换排序的排序过程及时间复杂度的分析方法。

2022.5.22记录：Code_流苏(CSDN)
如有任何疑问，评论回复，看到即回，欢迎大家多多交流学习！
★以上实验内容仅供参考。