Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >经典算法巡礼(二) -- 排序之选择排序

经典算法巡礼(二) -- 排序之选择排序

原创
作者头像
jiezhu
修改于 2018-09-17 03:54:53
修改于 2018-09-17 03:54:53
4770
举报
文章被收录于专栏:codingforevercodingforever

选择排序,如冒泡排序一样,从名字中即可大概猜测其排序的原理。其工作原理就是从未排序的数组中选出最大(小)的元素,将其放置至数组的首(尾)部,重复此过程直至没有未排序的子数组。

当然,在分析该排序算法前还是先将golang实现版本放置出来献下丑:

代码语言:txt
AI代码解释
复制
	// Sort方法从数组头开始,将未排序的元素做为子数组,并在子数组中选择中最小的元素,将其放置子数组的最首位置做为已排序元素,重复此过程,直到所有数组元素排序完成为止
	// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
	func (this *SelectSort) Sort(a []Comparable, compare Compare) {
		for i := 0; i < len(a); i++ {
			min := i
			for j := i + 1; j < len(a); j++ {
				if this.less(a[j], a[min], compare) == true {
					min = j
				}
			}
			this.exch(a, i, min)
		}
	}

同样,我们用与冒泡排序相同的方法分析其效率。观察选择排序的代码实现,明显她也是时间复杂度为O(N^2)的排序算法。同样以元素比较作为单元操作,完成一个长度为N的数组的排序工作需要N-1 + N-2 + ... + 2 + 1次比较操作,简化后为(N-1)/2*N = (N^2-N)/2 ~ N^2

冒泡排序不同的是,虽然两种排序算法的比较次数是相同的,但是其元素交换操作数目并不是相同的。选择排序的交换操作最多为N次,而冒泡排序的交换操作却与数组中不满足顺序的元素对数量相同,即与被排序数组相关,在最差情况下,其次数与比较次数相同,即N^2

虽然选择排序在元素交换方面比冒泡排序具有一定的优势,但是其时间复杂度依然是万恶的平方级别的,即O(N^2),所以其依然只适用于小型数组的排序,不能满足大量数据的排序

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
经典算法巡礼(三) -- 排序之插入排序
插入排序,与之前的冒泡排序和选择排序一样,其名称就说明了她的原理。所谓插入排序,就是对于数组中未排序的元素,依次遍历寻找合适的位置并插入到已排序的子数组中。当数组中没有未排序的元素时,插入排序即完成。
jiezhu
2018/09/02
3360
经典算法巡礼(一) -- 排序之冒泡排序
事实上,她重复地遍历需要排序的元素,一次比较相邻的两个元素,如果不满足预先定义的比较条件,则交换;否则继续下一组元素比较,直至遍历完成需要排序的所有元素。当然,遍历需要排序的元素需要重复进行,直到没有需要排序的元素为止。遍历需要排序的元素时,每一次交换不满足顺序条件的元素就如同气泡一样,从元素序列的一端慢慢“上升”到序列的另一端,此现象如同水中冒气泡一样,此排序算法以此得名。
jiezhu
2018/09/02
3680
经典算法巡礼(四) -- 排序之希尔排序
希尔排序与之前的排序算法不同,她是以她的发明者Donald Shell来命名的。她是插入排序的一种改进版本。
jiezhu
2018/09/02
4410
排序之简单排序
在元素之间进行比较,而Java提供了一个接口Comparable就是用来定义排序规则的。
Rochester
2020/09/01
4640
排序之简单排序
经典算法巡礼(五) -- 排序之归并排序
归并排序是创建在归并操作上的一种有效排序算法。所谓归并操作,指的是将两个已经排序的序列合并成一个序列的操作。归并排序是分治思想的典型示范。
jiezhu
2018/09/02
3260
经典算法巡礼(六) -- 排序之快速排序
快速排序正如她的名字,她是一种排序效率相当高的算法,而且可能是应用最广泛的排序算法了。快速排序流行的原因是她实现简单,适用于各种不同的输入数据且在一般应用中比其他排序算法都要快。不仅如此,她与归并排序不同,她只需要很小的辅助空间就可以进行排序。
jiezhu
2018/09/02
4370
算法02 七大排序之:直接选择排序和堆排序
上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、堆排序及算法实现 1、直接选择排序及算法实现 直接选择排序(Straight Select Sort) 是一种简单的排序方法,它的基本思想是:通过length-1 趟元素之间的比较,从length-i+1个元素中选出最小的元素,并和第i个元素交换位置。直接选择排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n2)    下图展示了直接选择排序的
nnngu
2018/03/15
6840
算法02 七大排序之:直接选择排序和堆排序
普林斯顿大学算法公开课笔记——选择排序 普林斯顿大学算法公开课笔记——选择排序
简单选择排序的特点是交换移动次数很少(至多n-1次),其时间复杂度为 O(n²) (时间主要花在比较上,总的比较次数为N=(n-1)+(n-2)+…+1=n*(n-1)/2),与冒泡排序一样,但性能上优于冒泡。
尾尾部落
2018/09/04
6390
动图解析面试常见排序算法(上)
冒泡排序是一种非常简单的初级排序算法,它每次比较相邻的两个元素,如果顺序错误就进行交换.由于最小的元素是经由不断交换慢慢浮到顶端的,所以叫做冒泡排序.
周三不加班
2019/06/04
4860
动图解析面试常见排序算法(上)
#算法基础#选择和插入排序
算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第二篇《选择和插入排序》,非常赞!希望对大家有帮助,大家会喜欢! 系列文章: 由快速排序到分治思想 一、选择排序 这是一种最简单的排序算法 第一步他先找到数组中最小的元素,然后将它和本数组中第一个元素交换位置。然后把剩下的n-1个数算为一个数组。继续找到其中最小的 放到第二个位置。以此往复。于是恭喜你得到了大奖,一个有序的数组。哈哈 话不多说 看代码 : public static void sort(Comparable[] a)
大数据和云计算技术
2018/03/08
7520
经典算法巡礼(七) -- 排序之堆排序
很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现在时间最近的定时器即可,定时器触发时间无须全部有序,只需要处理优化级最高的定时器即可。
jiezhu
2018/09/02
5250
排序算法总结
概述  本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示: 选择排序 种最简单的排序算
Kevin_Zhang
2018/07/05
7620
一文弄懂七种排序算法
本文介绍了七种经典排序算法,包括冒泡排序,选择排序,插入排序,希尔排序,归并排序,快速排序以及堆排序,并且讨论了各种算法的进一步改进,在文章最后还对所有算法的时间和空间复杂度作了一个总结。
zhayujie
2020/06/16
1.1K0
算法一看就懂之「 选择排序 」
上一篇文章咱们已经聊过「 冒泡排序 」和「 插入排序 」了,今天我们来看一看「 选择排序 」。「 选择排序 」虽然在实际应用中没有「 插入排序 」广泛,但它也是我们学习排序算法中必不可少的一种。「 冒泡排序 」和「 插入排序 」都是在两层嵌套循环中慢慢比较元素,不停的调整元素的位置。而「 选择排序 」就比较直接了,属于不出手则已,一出手,相应的元素就必须要到位,元素的位置就不会再变了。
奎哥
2019/11/10
5230
【愚公系列】2023年11月 十一大排序算法(五)-选择排序
排序算法是一种将一组数据按照特定的规则进行排列的方法。排序算法通常用于对数据的处理,使得数据能够更容易地被查找、比较和分析。
愚公搬代码
2023/11/24
2380
我们真的搞懂这些排序算法了吗?(一)
或许你已经学过了这些常见的排序算法,或者你看过了别人写的文章,但是这篇文章绝对不会浪费你的时间,一定会有所收获的。
godweiyang
2021/02/24
4830
我们真的搞懂这些排序算法了吗?(一)
【数据结构与算法】简单排序(冒泡排序、选择排序、插入排序)完整思路
本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接
@零一
2021/01/29
4730
Python 算法基础篇:冒泡排序和选择排序
冒泡排序和选择排序是两种常用的排序算法,用于将一个无序列表按照特定顺序重新排列。本篇博客将介绍冒泡排序和选择排序的基本原理,并通过实例代码演示它们的应用。
小蓝枣
2023/07/24
4760
极客算法训练笔记(六),十大经典排序之希尔排序,快速排序
排序算法的衡量指标我这里不再重复,上一篇我已经列举分析的很清楚了,但是非常重要,没看到我上一篇的小伙伴墙裂推荐,这里给一个直通车票 极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序 。
阿甘的码路
2020/11/12
5170
极客算法训练笔记(六),十大经典排序之希尔排序,快速排序
Java数组全套深入探究——进阶知识阶段2、冒泡排序
总篇链接:https://laoshifu.blog.csdn.net/article/details/134906408
红目香薰
2023/12/11
2440
Java数组全套深入探究——进阶知识阶段2、冒泡排序
推荐阅读
相关推荐
经典算法巡礼(三) -- 排序之插入排序
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档