用C语言进行学生成绩排序(简单选择排序和对堆排序)

这篇具有很好参考价值的文章主要介绍了用C语言进行学生成绩排序(简单选择排序和对堆排序)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.选择排序

选择排序的基本思想是:每一趟(如第i趟)在后面n-i+1 (i=1,2…,n-1) 个待排序元素中选取关键字最小的元素,作为有序子序列的第i个元素,直到第n-1趟做完,待排序元素只剩下1个,就不用再选了。选择排序中的堆排序算法是历年考查的重点。

二.简单选择排序

1.算法思想

根据上面选择排序的思想,可以很直观地得出简单选择排序算法的思想:假设排序表为[L…n],第i趟排序即从Li.n]中选择关键字最小的元素与I(i)交换,每-趟排序可以确定一个元素的最终位置,这样经过n-1趟排序就可使得整个排序表有序。

2.算法实现

//简单选择排序
void selectsort(SqList &L){
	for(int i=0;i<L.length-1;i++){      //一共进行n-1趟
		Elemtype min=L.data[i];        //记录最小的元素位置
		int n=0;
		for(int j=i+1;j<L.length;j++){  //从未排序部分开始遍历
			if(L.data[j].grade<min.grade) {
				min=L.data[j];
				n=j;
			}
		}
		if(min.grade!=L.data[i].grade){
			Elemtype temp=L.data[i];
			L.data[i]=L.data[n];
			L.data[n]=temp;
		}
	}
}

3.效率分析

简单选择排序算法的性能分析如下:

  • 空间效率:仅使用常数个辅助单元,故空间效率为0(1)。,
  • 时间效率:从上述伪码中不难看出,在简单选择排序过程中,元素移动的操作次数很少,不会超过3(n- 1)次,最好的情况是移动0次,此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关,始终是n(n- 1)/2次,因此时间复杂度始终是0(n2 )。
  • 稳定性:在第i趟找到最小元素后,和第i个元素交换,可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如,表L= {2,2,1},经过一趟排序后L={1,2,2},最终排序序列也是L={1,2,2},显然,2与2的相对次序已发生变化。因此,简单选择排序是一种不稳定的排序方法。

三.堆排序

1.算法思想

堆排序的思路很简单:首先将存放在L1…n]中的n个元素建成初始堆,由于堆本身的特点(以大顶堆为例),堆顶元素就是最大值。输出堆顶元素后,通常将堆底元素送入堆顶,此时根结点已不满足大顶堆的性质,堆被破坏,将堆顶元素向下调整使其继续保持大顶堆的性质,再输出堆顶元素。如此重复,直到堆中仅剩-一个元素为止。可见堆排序需要解决两个问题:①如何将无序序列构造成初始堆?②输出堆顶元素后,如何将剩余元素调整成新的堆?

堆排序的关键是构造初始堆。n个结点的完全二二叉树,最后一个结点是第Ln/2」个结点的孩子。对第Ln/2」个结点为根的子树筛选(对于大根堆,若根结点的关键字小于左右孩子中关键字较大者,则交换),使该子树成为堆。之后向前依次对各结点(Ln/2J-1~1)为根的子树进行筛选,看该结点值是否大于其左右子结点的值,若不大于,则将左右子结点中的较大值与之交换,交换后可能会破坏下一级的堆,于是继续采用上述方法构造下一-级的堆,直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆,直到根结点。

2.调整示例

初始时调整L(4)子树,09 < 32,交换,交换后满足堆的定义;向前继续调整L(3)子树,78<左右孩子的较大者87,交换,交换后满足堆的定义;向前调整L(2)子树,17 <左右孩子的较大者45,交换后满足堆的定义;向前调整至根结点L(1),53 <左右孩子的较大者87,交换,交换后破坏了L(3)子树的堆,采用上述方法对L(3)进行调整,53<左右孩子的较大者78,交换,至此该完全二叉树满足堆的定义。

用C语言进行学生成绩排序(简单选择排序和对堆排序),数据结构与算法,c语言,排序算法,算法,数据结构

3.C语言实现

void Heapsort(SqList &L){
	buildMaxheap(L);
	for(int i=L.length-1;i>0;i--){
		Elemtype temp=L.data[i];
		L.data[i]=L.data[0];
		L.data[0]=temp;
		HeadAdjust(L,0, i);
	}
}

4.效率分析

堆排序算法的性能分析如下:

  • 空间效率:仅使用了常数个辅助单元,所以空间复杂度为0(1)。
  • 时间效率:建堆时间为O(n),之后有n-1次向下调整操作,每次调整的时间复杂度为O(h),故在最好、最坏和平均情况下,堆排序的时间复杂度为O(nlog2n)。
  • 稳定性:进行筛选时,有可能把后面相同关键字的元素调整到前面,所以堆排序算法是一种不稳定的排序方法。例如,表L= {1, 2, 2},构造初始堆时可能将2交换到堆顶,此时L= {2, 1,2},最终排序序列为L={1,2,2},显然,2与2的相对次序已发生变化。

四.C语言实现完整示例

/*我们今天的主角插入排序是基于查找算法来的,所以我们还是利用线性表来进行模拟*/

/*为了便于我们后面演示希尔排序,所以我们采用顺序存储结构*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MaxSize 50                //这里只是演示,我们假设这里最多存五十个学生信息

//定义学生结构
typedef struct {
	char name[200];              //姓名
	int  grade;               //分数,这个是排序关键字
} Elemtype;

//声明使用顺序表
typedef struct {
	/*这里给数据分配内存,可以有静态和动态两种方式,这里采用动态分配*/
	Elemtype  *data;            //存放线性表中的元素是Elemtype所指代的学生结构体
	int length;                 //存放线性表的长度
} SqList;						//给这个顺序表起个名字,接下来给这个结构体定义方法

//初始化线性表
void InitList(SqList &L){
	/*动态分配内存的初始化*/
	L.data = (Elemtype*)malloc(MaxSize * sizeof(Elemtype));  //为顺序表分配空间
	L.length = 0;                                            //初始化长度为0
}

//求表长函数
int Length(SqList &L){
	return L.length;
}

//求某个数据元素值
bool GetElem(SqList &L, int i, Elemtype &e) {
	if (i < 1 || i > L.length)
		return false;         //参数i错误时,返回false
	e = L.data[i - 1];      //取元素值
	return true;
}

//输出线性表
void DispList(SqList &L) {
	if (L.length == 0)
		printf("线性表为空");
	//扫描顺序表,输出各元素
	for (int i = 0; i < L.length; i++) {
		printf("%s        %d", L.data[i].name,  L.data[i].grade);
		printf("\n");
	}
	printf("\n");
}

//插入数据元素
bool ListInsert(SqList &L, int i, Elemtype e) {
	/*在顺序表L的第i个位置上插入新元素e*/
	int j;
	//参数i不正确时,返回false
	if (i < 1 || i > L.length + 1 || L.length == MaxSize)
		return false;
	i--;                //将顺序表逻辑序号转化为物理序号
	//参数i正确时,将data[i]及后面的元素后移一个位置
	for (j = L.length; j > i; j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i] = e;      //插入元素e
	L.length++;         //顺序表长度加1
	return true;
	/*平均时间复杂度为O(n)*/
}

//简单选择排序
void selectsort(SqList &L){
	for(int i=0;i<L.length-1;i++){      //一共进行n-1趟
		Elemtype min=L.data[i];        //记录最小的元素位置
		int n=0;
		for(int j=i+1;j<L.length;j++){  //从未排序部分开始遍历
			if(L.data[j].grade<min.grade) {
				min=L.data[j];
				n=j;
			}
		}
		if(min.grade!=L.data[i].grade){
			Elemtype temp=L.data[i];
			L.data[i]=L.data[n];
			L.data[n]=temp;
		}
	}
}

void HeadAdjust(SqList &L,int k, int len){
	Elemtype temp=L.data[k];
	for(int i=2*k+1;i<len;i=2*i+1){
		if(i<len-1 && L.data[i].grade<L.data[i+1].grade)
			i++;
		if(temp.grade>=L.data[i].grade)
			break;
		else{
			L.data[k]=L.data[i];
			k=i;
		}
	}
	L.data[k]=temp;
}

void buildMaxheap(SqList &L){
	for(int i=L.length/2-1;i>=0;i--)
		HeadAdjust(L, i, L.length);
}

void Heapsort(SqList &L){
	buildMaxheap(L);
	for(int i=L.length-1;i>0;i--){
		Elemtype temp=L.data[i];
		L.data[i]=L.data[0];
		L.data[0]=temp;
		HeadAdjust(L,0, i);
	}
}

int main(){
	SqList L;
	Elemtype stuents[10]={{"张三",649},{"李四",638},{"王五",665},{"赵六",697},{"冯七",676},
		{"读者",713},{"阿强",627},{"杨曦",649},{"老六",655},{"阿黄",604}};
	//这一部分忘了的请回顾我的相关博客
	printf("初始化顺序表并插入开始元素:\n");
	InitList(L);         //这时是一个空表,接下来通过插入元素函数完成初始化
	for (int i = 0; i < 10; i++)
		ListInsert(L, i + 1, stuents[i]);
	DispList(L);
	/*printf("根据分数进行简单选择排序后结果为:\n");
	selectsort(L);
	DispList(L);          //到这一步我们的简单选择排序没什么问题的
	 */
	printf("根据分数进行堆排序后结果为:\n");
	Heapsort(L);
	DispList(L);
}

五.运行结果

1.简单选择排序

用C语言进行学生成绩排序(简单选择排序和对堆排序),数据结构与算法,c语言,排序算法,算法,数据结构

2.堆排序

用C语言进行学生成绩排序(简单选择排序和对堆排序),数据结构与算法,c语言,排序算法,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-549871.html

到了这里,关于用C语言进行学生成绩排序(简单选择排序和对堆排序)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言课程设计:学生成绩信息管理系统(排序、平均分、总分)详解

    1、需求分析 利用C语言编写一个可以对学生成绩信息进行管理的系统 0、退出系统 1、录入学生信息和成绩 2、打印学生信息 3、统计学生人数 4、查找学生信息 5、修改学生信息 6、删除学生信息 7、排序学生成绩 8、生成学生信息文件 9、读取文件学生信息 10、输出各科成绩不

    2024年02月11日
    浏览(50)
  • C语言程序设计:某班有5名同学,建立一个学生的简单信息表,包括学号、姓名、3门课程的成绩,编写程序,计算每名学生的平均成绩及名次。

    题目内容: 某班有5名同学,建立一个学生的简单信息表,包括学号、姓名、3门课程的成绩,编写程序,计算每名学生的平均成绩及名次。(注:定义一个结构体类型,用结构指针作为函数参数) 输入格式: %ld %s %f %f %f 输出格式: %-9ld%-10s%-5.1f%-5.1f%-8.1f%-10.1f%-dn 输入样例:

    2024年02月02日
    浏览(42)
  • Python学生成绩排序(循环实现)

    题目要求 (成绩数据已给出) 输入学生成绩信息序列,完成对于每个学生成绩数据的储存,并将所有学生储存于列表中;在此基础上,按照总分从高到低的学生名单,总分从低到高的学生名单,三门课成绩从高到低的学生名单   相同成绩都按先录入排列在前的规则处理。

    2024年02月08日
    浏览(39)
  • 简单选择排序——C语言实现

    选择排序思想:若按照递增顺序对顺序表进行排列,在n个元素的顺序表中,从第i(i=1)个元素开始遍历到第n-1个元素,在遍历过程中都将第i个元素依次与第i+1到第n个元素进行比较,确定最小的元素,如果最小的元素不是第i个元素则将其与最小的元素进行交换。 代码如下:

    2024年02月11日
    浏览(32)
  • 查找和排序算法的学生成绩分析实验

    编写程序将自己学号后面的8位同学的学号、姓名以及数学、英语和数据结构的成绩信息保存到学生成绩表中。 学号 姓名 数学 英语 数据结构 189000202 张三 80 75 86 189000203 李四 55 63 72 189000204 王一 88 75 85 189000205 王二 79 96 83 189000206 王三 87 45 77 189000207 王四 66 56 50 189000208 王五

    2024年02月11日
    浏览(48)
  • 在c语言中使用链表完成学生成绩管理系统(密码登录系统的采纳,加入了隐藏与删除功能,添加了指针域与数据域两种不同的排序)

    #二、每个函数的简绍与思路 ##1:密码登录的验证思路: (1)在主函数main里定义一个标志 flat2=0;如果flat2!=0,就代表密码登录成功,可以进入系统! (2)在具体函数mima()之中,使用了控制台函数_getch();其头文件为#includeconio.h,该函数可以隐藏输出,注意:_getch()是隐藏单

    2024年04月23日
    浏览(39)
  • 学生成绩管理系统(合并文件,查找,总分排序,保存补考学生信息)

    目录 题目及要求: 录入学生成绩信息到链表中 合并文件 直接插入排序(总分降序) 冒泡排序(总分降序) 顺序查找(名字查找) 二分查找(名字查找)  这里是先按字母首字母排序再查找 保存不及格学生到文件中 现有学生成绩信息文件 1(1.txt),内容如下(同学自己补

    2024年02月10日
    浏览(44)
  • C语言经典算法之简单选择排序算法

    目录 前言 建议: 简介: 一、代码实现 二、时空复杂度: 时间复杂度: 空间复杂度: 三、算法的特性: 四、总结 1.学习算法最重要的是理解算法的每一步,而不是记住算法。            2.建议读者学习算法的时候,自己手动一步一步地运行算法。 简单选择排序是一种

    2024年01月19日
    浏览(40)
  • Python123:统计学生成绩、统计学生平均成绩与及格人数、成绩转换(C语言)

    1、统计学生成绩 题目 :本题要求编写程序读入N个学生的百分制成绩,统计五分制成绩的分布。百分制成绩到五分制成绩的转换规则: 大于等于90分为A; 小于90且大于等于80为B; 小于80且大于等于70为C; 小于70且大于等于60为D; 小于60为E。 输入格式: 输入在第一行中给出

    2024年02月06日
    浏览(59)
  • Python入门——学生成绩管理系统(录入、查找、删除、修改、排序、统计、显示)

    学生成绩管理系统主要包括录入学生信息、查找学生信息、删除学生信息、修改学生信息、排序、统计学生总人数、显示学生信息和退出系统。 系统界面编写(菜单显示函数): main函数:  录入学生信息函数: 查找学生信息函数: 删除学生信息函数:  修改学生信息函数

    2024年02月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包