实验八排序算法的实现与分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了实验八排序算法的实现与分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

实验八排序算法的实现与分析
一．实验目的
1.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；
2.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；
3.了解各种方法的排序过程及其时间复杂度的分析方法。
二、实验内容
统计成绩：给出 n 个学生的考试成绩表，每条信息由姓名和分数组成，试设
计一个算法：
1.按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同
一名次；
2.按名次列出每个学生的姓名与分数。

三、实验实习设备及开发环境
Visual studio 2022
四．实验实习过程步骤（注意是主要关键步骤，不是所有步骤，适当文字+截图说明）
Function1：插入排序。这里利用的带有哨兵的插入排序（因为我们在初始化的时候就已经把数组的开始设置成了下标为1开始，所以哨兵就可以放到下标为0的位置），我们从第二个位置开始，依次比较前一个(前面的序列我们默认为已经排序好的），首先我们将处于i位置的放在哨兵位置，就是下标为0的位置，然后，我们从后面依次比较，同时将比较的结果往后移动一位，当前面某个位置分数小于我们哨兵的时候，我们就可以插入了。
实验八排序算法的实现与分析,数据结构实验,排序算法,算法

Function2：冒泡排序。冒泡排序是比较相邻的两个元素，这里实现的从小到大排序，所以后面的score大于前面的score时，我们就要交换位置。
实验八排序算法的实现与分析,数据结构实验,排序算法,算法

Function3：选择排序。选定一个数据，然后比较后面的所有的数据，选择一个最小的数据，然后交换，依次选择交换下去，排序完毕。
实验八排序算法的实现与分析,数据结构实验,排序算法,算法

Function4：希尔排序。先分组，后排序。分组的gap是按照长度除以2依次分组，然后分组后进行直接插入排序。
在这里插入图片描述

五．实验实习结果及分析
实验八排序算法的实现与分析,数据结构实验,排序算法,算法

实验成功。

六．实验遇到的问题及解决办法，实验心得体会及对此实验的意见或建议（有就写，无可不写）。
源码：文章来源地址https://www.toymoban.com/news/detail-811807.html

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 10

typedef struct student
{
	char name[MAX];
	float score;
}Student;

int Initstudent(Student* s)
{
	printf("请输入学生信息。\n");
	char name[MAX];
	float score;
	int number = 0;
	while (scanf(" %s %f",name ,&score ) && strcmp(name, "0") &&  score!= 0)
	{
		number++;
		strcpy(s[number].name, name);
		s[number].score = score;
	}
	return number;
}

void insertsort(Student* s,int number)
{
	int i;
	int j;
	for (i = 2; i <= number; i++)
	{
		if (s[i].score < s[i - 1].score)
		{
			s[0].score = s[i].score;
			strcpy(s[0].name, s[i].name);
			for (j = i - 1;s[j].score>s[0].score ; j--)
			{
				s[j + 1].score = s[j].score;
				strcpy(s[j + 1].name, s[j].name);
			}
			s[j + 1].score = s[0].score;
			strcpy(s[j + 1].name, s[0].name);
		}
	}

}

void bubblesort(Student* s, int number)
{
	int i, j;
	int temp_score;
	char temp_name[MAX];
	for (i =2;i<=number;i++ )
	{
		for (j = 1; j<=number-1;j++)
		{
			if (s[j + 1].score < s[j].score)
			{
				temp_score = s[j + 1].score;
				s[j + 1].score = s[j].score;
				s[j].score = temp_score;
				strcpy(temp_name, s[j + 1].name);
				strcpy(s[j + 1].name, s[j].name);
				strcpy(s[j].name, temp_name);
			}
		}
	}
}

void printresult(Student* s, int number)
{
	int i;
	int level = 0;
	for (i = number; i >= 1; i--)
	{
		if (s[i].score == s[i + 1].score && i != number) 
		{
			printf("%d %s %.2f\n", level, s[i].name, s[i].score);
		}
		else
		{
			level++;
			printf("%d %s %.2f\n", level, s[i].name, s[i].score);
		}
	}
}

void swap(Student* s1, Student* s2)
{
	Student temp;
	temp = *s1;
	*s1 = *s2;
	*s2 = temp;
}

void choosesort(Student* s, int number)
{
	int i;
	float min;
	int min_key;
	int j;
	for (i = 1; i < number; i++)
	{
		min = s[i].score;
		for (j = i + 1; j <= number; j++)
		{
			if (s[j].score < min)
			{
				min = s[j].score;
				min_key = j;
			}
		}
		swap(&s[i], &s[min_key]);
	}
}

void shell(Student* s, int gap, int number)
{
	int i;
	for (i = gap; i <= number; i++)
	{
		Student tmp = s[i];
		int j = i - gap;
		for (j = i - gap; j >= 1; j = j - gap)
		{
			if (s[j].score > tmp.score)
			{
				s[j + gap] = s[j];
			}
			else
			{
				break;
			}
		}
		s[j + gap] = tmp;
	}
}

void shellsort(Student* s, int number)
{
	int lenth = number;
	while (lenth >= 1)
	{
		lenth = lenth / 2;
		shell(s, lenth,number);
	}
}


int main()
{
	Student s[MAX];
	int student_number;
	student_number = Initstudent(s);
	int choice;
	printf("请选择排序类型：1.插入排序，2.冒泡排序,3.选择排序,4.希尔排序\n");
	scanf("%d", &choice);
	if (choice == 1)
	{
		insertsort(s, student_number);
	}
	else if (choice == 2)
	{
		bubblesort(s, student_number);
		
	}
	else if (choice == 3)
	{
		choosesort(s, student_number);
	}
	else if (choice == 4)
	{
		shellsort(s, student_number);
	}
	else
	{
		printf("输入不正确\n");
		return 0;
	}
	printresult(s, student_number);
	return 0;

}