实验八 排序算法的实现与分析

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

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

Function2：冒泡排序。冒泡排序是比较相邻的两个元素，这里实现的从小到大排序，所以后面的score大于前面的score时，我们就要交换位置。

Function3：选择排序。选定一个数据，然后比较后面的所有的数据，选择一个最小的数据，然后交换，依次选择交换下去，排序完毕。

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

五．实验实习结果及分析

实验成功。

六．实验遇到的问题及解决办法，实验心得体会及对此实验的意见或建议（有就写，无可不写）。
源码：

#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;

}