当前位置: 首页 > 技术随笔 > 选择排序入门详解

选择排序入门详解

前面我们已经介绍了冒泡排序,接着我们来看看选择排序法

同样的,我们还是以冒泡排序中五名运动员的身高A(181)、B(169)、C(187)、D(172)、E(163)为例,然后使用选择排序法,对其实现从左到右、从低到高的排序。

与冒泡排序不同的是,选择排序法并不是让相邻的两名运动员按照顺序依次比较身高来得出排序结果。下面,我们来详细了解一下选择排序法的排序过程。

由于5名运动员需要按照从左到右、从低到高的顺序进行排序,因此最左边的位置应该属于身高最小的运动员。为了找出身高最小的运动员,教练需要找出最小身高的运动员和它的位置,以便于届时让该运动员与左边第1位的运动员交换位置。

现在教练先让左起第1位的运动员A(181)报出自己的身高,教练将其记录下来他的身高A(181)和位置(1)。
当前的记录为:运动员=A(181),位置=1
然后,教练又继续让左起第2位的运动员B(169)报出自己的身高,接着教练将B报出的身高与记录上A的身高进行比较,由于B的身高比A小,因此教练抹掉原来记录上A的身高和位置,并记录上B的身高(169)和位置(2)来代替。
当前的记录为:运动员=B(169),位置=2
同样的,教练又继续让左起第3位的运动员C(187)报出自己的身高,教练也将C报出的身高与记录上B的身高进行比较,由于C的身高比B大,所以教练不需要替换记录。
当前的记录为:
运动员=B(169),位置=2
接着,教练又继续让左起第4位的运动员D(172)报出自己的身高,教练也将D报出的身高与记录上B的身高进行比较,由于D的身高比B大,所以教练仍然不用替换记录。
当前的记录为:
运动员=B(169),位置=2
最后,教练又继续让左起第5为的运动员E(163)报出自己的身高,教练也将E报出的身高与记录上B的身高进行比较,由于E的身高比B小,所以教练抹掉记录上B的身高和位置,用E的身高和位置来代替。
当前的记录为:
运动员=E(163),位置=5

经过第一轮选择比较后,教练就知道了5名运动员中身高最小的运动员是E(163),他的位置是左起第5位。由于身高最小的运动员应该站在左起第1位,因此教练让E和左起第1位的A(181)交换位置:
E(163)、A(181)、B(169)、C(187)、D(172)

现在身高最小的运动员就已经确定了,并且已经站在了正确的位置上。接着,教练继续用上面的方法,从右边4名运动员中筛选出身高排名第4(倒数第2)的运动员记录,记录为:运动员=B(169),位置=3,因此教练让运动员B与左起第2为的A(181)交换位置:
E(163)、B(169)、A(181)、C(187)、D(172)

这样身高第5(最小)和身高第4的运动员就一定按照排序要求确定好位置了。于是,教练继续如法炮制,从而使5名运动员都按照指定的要求完成了排序。

上面5名运动员的排序过程,实际上就是选择排序法的排序过程。

现在,我们仍然用Java来实现使用选择排序法对上述5名运动员的身高进行排序:

// =====使用选择排序法对表示5名运动员身高的数组heights进行从低到高的排序=====

// A(181)、B(169)、C(187)、D(172)、E(163)
int[] heights = { 181, 169, 187, 172, 163 };
int count = heights.length; // 参与排序的运动员总人数

for (int i = 0; i < count; i++) {	// 外层循环控制教练记录身高的轮次数
	int minIndex = i;	//教练记录的位置
	int minHeight = heights[i];	//教练记录的运动员身高
	
	//内层循环控制本轮运动员的每一次报数和教练的记录工作
	for (int j = i + 1; j < count; j++) {
		//如果当前报数的运动员身高比教练当前记录的身高要小,则重新记录
		if (minHeight > heights[j]) {
			minHeight = heights[j];
			minIndex = j;
		}
	}
	//本轮报数和记录完毕后,教练让记录上的运动员与正确目标位置的运动员交换位置
	heights[minIndex] = heights[i];
	heights[i] = minHeight;
}
// =====选择排序完成=====

// 输出排序结果:
for (int height : heights) {
	System.out.println(height);
}

上面的Java代码输出如下:

163
169
172
181
187
14 0
我们认为: 用户的主要目的,是为了获取有用的信息,而不是来点击广告的。因此本站将竭力做好内容,并将广告和内容进行分离,确保所有广告不会影响到用户的正常阅读体验。用户仅凭个人意愿和兴趣爱好点击广告。
我们坚信:只有给用户带来价值,用户才会给我们以回报。
CodePlayer技术交流群1CodePlayer技术交流群1

帮朋友打一个硬广告:

P2P网贷系统(Java版本) 新年低价大促销,多年P2P技术积累,系统功能完善(可按需定制,可支持第三方存管、银行存管),架构稳定灵活、性能优异、二次开发快速简单。 另可提供二次开发、安装部署、售后维护、安全培训等一条龙服务。

外行看热闹,内行看门道。可以自信地认为,在系统设计上,比市面上的晓风、迪蒙、方维、绿麻雀、国融信、金和盛等P2P系统要好。
深圳地区支持自带技术人员现场考察源代码、了解主要技术架构,货比三家,再决定是否购买。

也可推荐他人购买,一旦完全成交,推荐人可获得实际售价 10% 的返现。
有意向者,详情请 点击这里 联系,工作时间立即回复。