博客

本题是浙江理工大学ACM入队200题第四套中的A题,同时给出了冒泡排序和选择排序算法

我们先来看一下这题的题面.

由于是比较靠前的题目,这里插一句.各位新ACMer朋友们,请一定要养成仔细耐心看题的习惯,尤其是要利用好输入和输出样例.

• 样例相当于给你举了个具体的例子,可以帮助你更好的理解题目
• 样例会告诉你输入和输出的格式,你必须要在程序里以这样的格式输入和输出,否则会出问题
• 样例可以在你本地写完代码之后用作测试,来检查你的代码能否正常地运行(不过样例运行正确并不代表完全对了,可能输入其他的数据会出现别的问题)

题面

题目描述

输入3个整数，将它们从大到小输出。思路提示：假设输入a b c三个数，可以先找出最大数和a交换，确保a最大； 然后剩下两数中找出最大数和b交换，确保b最大；剩下的c就是最小数；输出a b c就是从大到小排列了（注意：自己和自己不交换，如a本身就是最大，就不需要和a交换的）。

输入

输入3个整数

输出

从大到小输出，中间用空格隔开

样例输入

2 5 1

样例输出

5 2 1

题目分析

尽管仁慈的叶教在题面中直接给出了这题的一种实现方法,但部分新朋友们可能依旧会有明明知道应该用什么思路但是无从下手的感觉.一道题目往往可以追溯(或者说抽象)成某一个或几个算法模型,这题之所以会让你无所下手是因为你无法准确定位到应该使用的算法,这不怪大家,因为这道题的算法模型其实是排序算法,不过是简化过的.这里我们不管叶教的提示,先从两个数的从大到小输出的简单问题的解决思路出发,分别推出这道题的两种做法,然后再在提高模块中推广之为两种泛用的排序算法,即冒泡排序和选择排序.

一些复杂的问题往往可以分解成较小的规模,先把小规模的问题解决,然后逐步推广到大问题,分而治之,这是很重要的分治思想,这题便可以从两个数从大到小(下称为降序)输出入手.

实现两个数的降序非常容易,如果a本身比b大,那么我们不需要做处理(已经降序),如果b比a大,那我们将a和b交换即可,局部代码如下:

	// 定义两个变量a,b并输入,此处略,下同
	if(a < b)
	{
		// 如果a比b小,那么交换a和b,使得a比b大,完成降序
		// 如果你无法理解交换,可以想象a是一杯可乐而b是一杯橙汁,你想要把可乐倒在橙汁杯子里并且把橙汁倒在可乐杯子里
		int t = a; // 现实中不可能实现直接互倒(在程序中部分数据类型可以做到,但用代码中的这种实现更好理解),先再取一个杯子,把可乐倒在空杯子里
		a = b; // 此时可乐杯子已空,把橙汁倒在可乐杯子里
		b = t; // 此时橙汁杯子已空,把可乐倒在橙汁杯子里
		// 此时已然完成互倒,即a,b变量成功交换
	}
	// 输出a,b,此处略,下同

相信此处两数降序大家都可以很容量理解吧,那么接下来我们从这里出发推出三数降序吧!注意跟着一起想哦!

思路一

我们先仔细回想一下我们两数交换的过程,我们在两数不满足降序的时候,将大的数向前交换,使得这两个数形成降序,那么对于三个数,我们一样可以通过不断将大数向前交换,使得三个数形成降序.

为了保证交换到最前面的是最大的数,我们需要从后往前两两比较(即先比较c和b,在交换完成后比较a和b),只有这样才能保证每次都是当前的一个数和后面部分的最大数进行比较和交换,一次性将最大数交换到第一个位置上(可以在纸上试试分别从前往后和从后往前分别交换3 4 5,你便明白了),此时便回到了前面两数降序的问题,我们用同样的方法实现之即可,局部代码如下:

	if(c < b)
	{
		int t= c;
		c = b;
		b = t;
	}
	// 此时b为原本b和c中的最大值
	// 将a和原本b和c中的最大值(即现在的b)比较并交换
	if(a < b)
	{
		int t = a;
		a = b;
		b = t;
	}
	// 此时a为3个数中的最大值

此时a已然是最大值,对于a而言已经完成局部降序了,接下来只要让b和c降序即可(此时b可能已经不是之前的b了,因为a可能已经与b交换了,而原本的a可能比c小,所以需要再操作一下),这个就很容易了,因为此时又转化为了两个数降序的问题了.

参考代码

下面给出了我自己用这种思路做这道题时候的完整代码:

(仅作为参考,一定要自己写一下奥,作弊没意思,害人又害己)

#include <stdio.h>

int main()
{
	int a, b, c;
	scanf("%d%d%d",&a, &b, &c);
	
	// 如果b比c小,那么交换b和c,使得b比c大,将大的数向前移动
	if(b < c)
	{
		// 如果你无法理解交换,可以想象b是一杯可乐而c是一杯橙汁,你想要把可乐倒在橙汁杯子里并且把橙汁倒在可乐被子里
		int t = b; // 现实中不可能实现直接互倒(在程序中部分数据类型可以做到,但用代码中的这种实现更好理解),先再取一个杯子,把可乐倒在空杯子里
		b = c; // 此时可乐杯子已空,把橙汁倒在可乐杯子里
		c = t; // 此时橙汁杯子已空,把可乐倒在橙汁杯子里
		// 此时已然完成互倒,即b,c变量成功交换
	}
	// 此时b为原本b和c中的最大值
	
	// 将a和原本b和c中的最大值(即现在的b)比较并交换
	if(a < b)
	{
		int t = a;
		a = b;
		b = t;
	}
	// 此时a为3个数中的最大值,已局部降序
	
	// 接着对现在的b和c进行同样的操作
	if(b < c)
	{
		int t = b;
		b = c;
		c = t;
	}
	
	printf("%d %d %d", a, b, c);
	
	return 0;
}

思路二

当然,我们可以换一种角度理解我们之前的两数交换,我们之所以在a小于b的时候把b换到a上去,是希望我们能在a(即第一个数)上保存当前最大的元素.

同样,对于三个元素,我们也可以做这样的操作,我们不断把a后面的元素b和c与a进行比较并交换(在这里从后往前还是从前往后就无所谓啦,因为每个元素都是单独和a(比较这个元素之前的局部最大值)比较的),这样完成这一轮比较后,a中保存的便是三个数中的最大值了,局部代码如下:

	if(a < b)
	{
		int t = a;
		a = b;
		b = t;
	}
	// 此时a为a和b中的最大值
	if(a < c)
	{
		int t = a;
		a = c;
		c = t;
	}
	// 此时a为a(a为a和b中的最大值)和c中的最大值,即三个数中的最大值

此时对于a而言同样已经完成局部降序了,接下来同样也只要让b和c降序即可,此时又转化为了两个数降序的问题了,这里同样直接沿用前面的两数降序的方法即可.

参考代码

下面给出了我自己用这种思路做这道题时候的完整代码:
(仅作为参考,一定要自己写一下奥,作弊没意思,害人又害己)

#include <stdio.h>

int main()
{
	int a, b, c;
	scanf("%d%d%d",&a, &b, &c);
	
	if(a < b)
	{
		int t = a;
		a = b;
		b = t;
	}
	// 此时a为a和b中的最大值
	if(a < c)
	{
		int t = a;
		a = c;
		c = t;
	}
	// 此时a为a(a为a和b中的最大值)和c中的最大值,即三个数中的最大值
	
	// 接着对现在的b和c进行同样的操作
	if(b < c)
	{
		int t = b;
		b = c;
		c = t;
	}
	
	printf("%d %d %d", a, b, c);
	return 0;
}

提高

我们从简单的两数降序,根据不同的理解推出了两种三数降序的方法,那我们可以把这两个方法推广到对n个数排序嘛?答案是肯定的.事实上,这里介绍的两种思路正是最基础的两种排序算法————冒泡排序和选择排序的基础思路(此处为了简化,选择排序使用了不设k的非标准版,如果想看标准的选择排序可以去谷歌或百度搜索).

冒泡排序算法

先来推广思路一,我们将会将其推广为冒泡排序算法.

我们先在三数的基础上变为四数,记为a,b,c,d,我们同样可以用思路1来处理,我们从d开始逐个向前比较,将大的数向前交换,完成这一轮交换后,就和三数交换一样,最大的数被交换到了a的位置,此时a局部有序.

之后,无序的便是后三个元素了,就回到了前面的三数降序了,我们使用同样的方法,从d开始逐个向前比较,将大的数向前交换,此时只要比到b即可,因为a已然局部有序,无需再操作了.此时a,b局部有序.

在之后便变成了两个数降序了,相信朋友们应该很熟悉了,此处省略.

由此我们可以发现,我们这种从后往前不断把最大数向前交换的思路可以对2个数起效,同时在n个数起效时可以保证对n+1个数也起效,根据数学归纳法,我们得出了一种可以适用于n个数的降序排序算法,我们称之为冒泡排序算法.

所谓冒泡,便是我们将最大值不断向前交换的过程,它就像水里的气泡冒到水面那样,很形象吧!

不过,保存n个数我们不采用n个变量,而是使用一个叫数组的东西,同样对这n个数我们也不会分别写出各个if语句,而是使用循环语句.或许看到这里的朋友还不会上述两个东西,不过不要紧,只要理解上述的思路,在之后理解了数组和循环后代码还是很好写的,下面给出局部参考代码:

	// len为数组a的长度,下同
	// 外循环表示当前冒泡排序的操作已完成几次,同时也表示已局部有序部分的长度
	for (int i = 0; i < len; i++)
	{
		// 内循环即为前面所说的冒泡操作了,每次从数组尾部开始与前一个元素比较,将较大元素不断向前交换,比较到第一个无序元素即可,因为前面均已局部有序了(即此时问题的规模已经从len减为len - i了)
		for(int j = len - 1;j > i;j--)
		{
			if(a[j - 1] < a[j])
			{
				int t = a[j];
				a[j] = a[j - 1];
				a[j - 1] = t;
			}
		}
	}

如果要实现升序(从小到大排序),也可以使用同样的格式,只要改变不等号的方向即可,大家可以自己写写看哦!

后面的诸如第十套的A,B题等都可以使用这种算法来完成,大家可以试试看.

选择排序算法

同样可以推广思路二,我们将会将其推广为选择排序算法.

我们同样先在三数的基础上变为四数,记为a,b,c,d,我们同样可以用思路2来处理,将除了a以外的每个数同a比较,如果比a大就交换,这样当一轮操作结束后,a中已然是所有数中的最大的那个了,此时a局部有序.

之后,无序的同样是后三个元素了,也就回到了前面的三数降序了,我们使用同样的方法,将除了a和b以外的(即b后面的)每个数同b比较,如果比b大就交换,这样当一轮操作结束后,b中已然是剩下的所有数中的最大的那个了,此时a,b局部有序.

在之后便变成了两个数降序了,相信朋友们应该很熟悉了,同样此处省略.

由此我们同样可以发现,我们这种不断和当前无序数据区域的第一个元素比较并交换的思路可以对2个数起效,同时在n个数起效时可以保证对n+1个数也起效,同样根据数学归纳法,我们又得出了一种可以适用于n个数的降序排序算法,我们称之为选择排序算法.

不过这里的选择排序并非标准的选择排序,而是一种不设k的非标准版本,目的是便于大家理解推出的过程.建议大家理解这一版本之后再去看一看这种算法的标准写法,可以加深对”选择”二字的理解.

同样保存n个数我们不采用n个变量,而是使用数组,也同样对这n个数我们也不会分别写出各个if语句,而是使用循环语句.或许看到这里的朋友还不会上述两个东西,不过不要紧,只要理解上述的思路,在之后理解了数组和循环后代码还是很好写的,下面给出局部参考代码:

	// 外循环表示当前选择排序的操作已完成几次,同时也表示当前需要将局部最大元素放在哪个位置
	for (int i = 0; i < len; i++)
	{
		// 内循环即为将i后面的所有元素和i这里的元素比较并交换,使得i位置储存这些数的最大值
		for(int j = i + 1;j < len;j++)
		{
			if(a[i] < a[j])
			{
				int t = a[i];
				a[i] = a[j];
				a[j] = t;
			}
		}
	}

如果要实现升序(从小到大排序),也可以使用同样的格式,只要改变不等号的方向即可,大家可以自己写写看哦!
后面的诸如第十套的A,B题等同样也都可以使用这种算法来完成,大家可以试试看.

补充

上述介绍的两种排序算法都是平方阶的排序算法,在实际写算法题和软件开发中是很少使用的,因为比较慢.在第十套的E题中会要求大家写一种叫插入排序的算法,这是对元素数量较少的数组排序时广泛采用的算法,而对于较多元素我们会选择其他的更快的线性对数阶的算法(比如快速排序、归并排序等,这些排序在处理大量元素是速度相对较快),比如C中stdlib里的qsort函数以及C++ STL算法库里的sort函数的内部实现都是一种快速排序.对这些排序算法感兴趣的同学们可以在网上搜索相关的文档了解一下哦!里面有不少有用的编程思想!

“正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯” —亚里士多德

这篇题解就到这里了,各位朋友如果有问题欢迎到acm成员群中提问哦!