★观前提示：本篇内容为数据结构实验，代码内容经测试没有问题，但是可能会不符合每个人实验的要求，因此以下内容建议仅做思路参考。
一、实验目的
（1）掌握常见的交换排序算法的思想及适用条件；
（2）掌握常见的交换排序算法的程序实现。
（3）了解各种交换排序的排序过程及其时间复杂度的分析方法。
二、实验要求
统计成绩： 给出 n 个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：
（1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；
（2） 按名次列出每个学生的姓名与分数。
★温馨提示：以下代码均为改正过的代码，皆已经过测试。
三、源码实现
1、冒泡排序和选择排序
#include<stdio.h>
#include<stdlib.h> //定义头文件
#include<string.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;//定义四个整型变量 n,i,k,t
student *a; //定义结构体指针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);//借助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 %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;
}
2、快速排序
#include<stdio.h>
#include<stdlib.h> //定义头文件
#include<string.h>
#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 %d\n",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<hight)
{
while(low<hight&&L.s[hight].score>=pivotkey)
{
hight=hight-1;
}
L.s[low]=L.s[hight];
while(low<hight&&L.s[low].score<=pivotkey){
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<hight){
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)
如有任何疑问，评论回复，看到即回，欢迎大家多多交流学习！
★以上实验内容仅供参考。
