首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >经典算法巡礼(二) -- 排序之选择排序

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

原创
作者头像
jiezhu
修改于 2018-09-17 03:54:53
修改于 2018-09-17 03:54:53
4690
举报
文章被收录于专栏: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
3330
经典算法巡礼(一) -- 排序之冒泡排序
事实上,她重复地遍历需要排序的元素,一次比较相邻的两个元素,如果不满足预先定义的比较条件,则交换;否则继续下一组元素比较,直至遍历完成需要排序的所有元素。当然,遍历需要排序的元素需要重复进行,直到没有需要排序的元素为止。遍历需要排序的元素时,每一次交换不满足顺序条件的元素就如同气泡一样,从元素序列的一端慢慢“上升”到序列的另一端,此现象如同水中冒气泡一样,此排序算法以此得名。
jiezhu
2018/09/02
3640
经典算法巡礼(六) -- 排序之快速排序
快速排序正如她的名字,她是一种排序效率相当高的算法,而且可能是应用最广泛的排序算法了。快速排序流行的原因是她实现简单,适用于各种不同的输入数据且在一般应用中比其他排序算法都要快。不仅如此,她与归并排序不同,她只需要很小的辅助空间就可以进行排序。
jiezhu
2018/09/02
4240
经典算法巡礼(四) -- 排序之希尔排序
希尔排序与之前的排序算法不同,她是以她的发明者Donald Shell来命名的。她是插入排序的一种改进版本。
jiezhu
2018/09/02
4360
经典算法巡礼(五) -- 排序之归并排序
归并排序是创建在归并操作上的一种有效排序算法。所谓归并操作,指的是将两个已经排序的序列合并成一个序列的操作。归并排序是分治思想的典型示范。
jiezhu
2018/09/02
3160
排序之简单排序
在元素之间进行比较,而Java提供了一个接口Comparable就是用来定义排序规则的。
Rochester
2020/09/01
4490
排序之简单排序
一文弄懂七种排序算法
本文介绍了七种经典排序算法,包括冒泡排序,选择排序,插入排序,希尔排序,归并排序,快速排序以及堆排序,并且讨论了各种算法的进一步改进,在文章最后还对所有算法的时间和空间复杂度作了一个总结。
zhayujie
2020/06/16
1.1K0
排序算法总结
概述  本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示: 选择排序 种最简单的排序算
Kevin_Zhang
2018/07/05
7520
动图解析面试常见排序算法(上)
冒泡排序是一种非常简单的初级排序算法,它每次比较相邻的两个元素,如果顺序错误就进行交换.由于最小的元素是经由不断交换慢慢浮到顶端的,所以叫做冒泡排序.
周三不加班
2019/06/04
4780
动图解析面试常见排序算法(上)
经典算法巡礼(七) -- 排序之堆排序
很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现在时间最近的定时器即可,定时器触发时间无须全部有序,只需要处理优化级最高的定时器即可。
jiezhu
2018/09/02
5210
普林斯顿大学算法公开课笔记——选择排序 普林斯顿大学算法公开课笔记——选择排序
简单选择排序的特点是交换移动次数很少(至多n-1次),其时间复杂度为 O(n²) (时间主要花在比较上,总的比较次数为N=(n-1)+(n-2)+…+1=n*(n-1)/2),与冒泡排序一样,但性能上优于冒泡。
尾尾部落
2018/09/04
6340
排序算法解析
排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括:
张小驰出没
2021/12/06
3880
排序算法解析
Python 算法基础篇:冒泡排序和选择排序
冒泡排序和选择排序是两种常用的排序算法,用于将一个无序列表按照特定顺序重新排列。本篇博客将介绍冒泡排序和选择排序的基本原理,并通过实例代码演示它们的应用。
小蓝枣
2023/07/24
4590
Python算法——选择排序
选择排序(Selection Sort)是一种简单的排序算法,它的基本思想是在未排序的部分中选择最小(或最大)的元素,然后将其放在已排序部分的末尾。选择排序不同于冒泡排序,它不需要反复交换元素,因此在某些情况下可能比冒泡排序更快。本文将详细介绍选择排序的工作原理和Python实现。
Echo_Wish
2023/11/30
3710
经典排序算法(二)选择排序
选择排序是一种简单排序算法。这是一个基于位置比较的算法,通常实现是左边是已经排好序的元素列表,右边是待排序的元素。当然,一开始的时候,我们认为都是未经排序的。
青山师
2023/05/04
4880
经典排序算法(二)选择排序
经典排序算法详细介绍
渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:
IT茂茂
2020/03/05
1.4K0
经典排序算法详细介绍
【数据结构与算法】简单排序(冒泡排序、选择排序、插入排序)完整思路
本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接
@零一
2021/01/29
4590
极客算法训练笔记(六),十大经典排序之希尔排序,快速排序
排序算法的衡量指标我这里不再重复,上一篇我已经列举分析的很清楚了,但是非常重要,没看到我上一篇的小伙伴墙裂推荐,这里给一个直通车票 极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序 。
阿甘的码路
2020/11/12
5060
极客算法训练笔记(六),十大经典排序之希尔排序,快速排序
常见算法之排序
各类排序算法,不仅是算法基本功,也是面试中永恒的考题,关于每种算法思想、实现(递归与非递归)以及时空复杂度分析是必须牢牢把握的送分题。本文先将排序算法按不同标准进行分类,随后依次详细介绍了直接插入、希尔、冒泡、快速、简单选择、堆、归并、基数与外部排序等经典排序算法,并在文末给出了各种排序方法的性能比较作为总结。本文全部代码实例可从此处获得。
我是东东东
2018/08/01
6950
C/C++ 常见数组排序算法
本文介绍了几种常见的排序算法的实现,包括冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序。冒泡排序通过多次遍历数组,比较并交换相邻元素,逐步将较小元素“浮”到数组顶端,时间复杂度为O(n^2)。选择排序通过选择未排序部分的最小元素进行交换,逐步完成整个数组排序,同样具有O(n^2)的时间复杂度。插入排序将数组分为已排序和未排序部分,逐个插入未排序元素到已排序部分的合适位置,时间复杂度为O(n^2)。希尔排序是插入排序的改进版本,通过分组插入排序,最终得到有序数组,时间复杂度在O(n log n)到O(n^2)之间。归并排序采用分治策略,递归拆分和合并数组,时间复杂度始终为O(n log n),但需要额外空间。最后,快速排序通过选择基准值划分数组,并递归排序子数组,平均时间复杂度为O(n log n),但最坏情况下为O(n^2)。这些算法各有特点,适用于不同场景。
王 瑞
2023/11/23
5840
相关推荐
经典算法巡礼(三) -- 排序之插入排序
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档