python排序算法之选择排序
作者:i阿极 发布时间:2023-03-15 11:56:56
一、前言
相关知识来自《python算法设计与分析》。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序3种。虽然它们的效率相对于高级排序算法偏低,但是在了解初级排序算法之后,再去学习相对复杂的高级排序算法会容易许多。本文介绍选择排序。
二、描述
选择排序表示从无序的数组中,每次选择最小或最大的数据,从无序数组中放到有序数组的末尾,以达到排序的效果。
选择排序的平均时间复杂度是O(n2),最好情况下的时间复杂度和最坏情况下的时间复杂度都是O( n2 )。另外,它是一个不稳定的排序算法。选择排序的过程很容易理解。如图2-4所示,我们仍以递增排序的算法为例,先遍历未排序的数组,找到最小的元素。然后,把最小的元素从未排序的数组中删除,添加到有序数组的末尾。
因为最小的元素是1,所以1被添加到仍为空的有序数组末尾。
如图2-5所示,我们继续对剩余元素进行遍历。这次,最小的元素是2。我们把它添加到已排序的数组末尾。由于已在有序数组中的元素必定小于未排序数组中的所有元素,所以这步操作是正确无误的。
如图2-6所示,重复上述步骤,当未排序数组中只剩下一个元素时,把它添加到已排序的数组末尾,整个数组的排序就完成了。
三、代码实现
选择排序代码:
nums = [5,3,6,4,1,2,8,7]
res = []#用于存储已排序元素的数组
while len(nums): #当未排序数组内还有元素时,重复执行选择最小数的代码
minInd = 0 #初始化存储最小数下标的变量,默认为第一个数
for i in range(1, len(nums)):
if(nums[i] < nums[minInd]): #更新最小数的下标
minInd = i
temp = nums[minInd]
nums.pop(minInd) #把最小数从未排序数组中删除
res.append(temp) #把最小数插入到已排序数组的末尾
print(res)
运行程序,输出结果为:
[1,2,3,4,5,6,7,8]
在程序中,第一个for循环中的i代表了有序数组之后的第一个位置,也就是未排序数组中的第一个位置。随后,再使用一个for循环,在未排序数组中找到最小值的下标。首先,把最小值下标minInd初始化为未排序数组中第一个元素的下标。随后,遍历整个数组,遇到比目前的最小值更小的元素时,更新下标即可。找出最小值后,把它和未排序数组中的第一个元素交换位置,这时它就成了有序数组中的最后一个元素。
来源:https://blog.csdn.net/AOAIYI/article/details/128632969
猜你喜欢
- HTTP(HyperTextTransferProtocol)是超文本传输协议的缩写,它用于传送WWW方式的数据,关于HTTP协议的详细内容
- 一个封装好的JavaScript拖动类,使用方便:<div id="idDrag" style="bor
- 需求说明当用户申请售后,商家未在n小时内处理,系统自动进行退款。商家拒绝后,用户可申请客服介入,客服x天内超时未处理,系统自动退款。用户收到
- 1. 用Dreamweaver 4.0轻松设计会自动弹性调整的网页 首先需要保证的是你的页面内容采用了表格的格式,然后打开你要编辑的页面,按
- 你的SQL Server最近是否运行不正常?不,我指的不是我们肯定会遇到的通常的数据库和操作系统问题。我的意思是,你是否经历过服务器的反应迟
- 有时候很多朋友访问自己的asp或php等程序页面时出现一些错误,就是页面无法显示也没有详细的错误信息,就算iis中开启了显示详细的错误也不能
- 在 MySQL 下,在进行中文模糊检索时,经常会返回一些与之不相关的记录,如查找 "%a%" 时,返回的可能有中文字符,
- ThinkPHP支持多种php模板引擎,可以根据个人需要加以配置。下面我们以Smarty模板引擎为例,给大家说说具体的操作流程!首先去Sma
- 定义和用法strftime() 函数根据区域设置格式化本地时间/日期。语法strftime(format,timestamp)参数 描述 f
- isset(PHP 3, PHP 4, PHP 5 )isset -- 检测变量是否设置描述bool isset ( mixed var [
- TO_NUMBER(char[,'format_model']) 字符转换到数字类型TO_DATE(char[,'f
- sql server的备份与恢复(查询分析器) 查询分析器: 命令: 1:备份数据库命令: backup database whdb1(要备
- 本文实例讲述了PHP利用func_get_args和func_num_args函数实现函数重载的方法。分享给大家供大家参考。具体方法分析如下
- 国产框架thinkPHP,是一款MVC框架,这个框架最初模拟JAVA的struts框架,使用单一入口文件模拟JAVA的过滤器,使用actio
- </pre><pre name="code" class="javascript"
- 下列语句部分是Mssql语句,不可以在access中使用。SQL分类:DDL—数据定义语言(CREATE,ALTER,DROP,DECLAR
- 最近一个小项目需要一个星级评分的效果,所以去淘宝偷了一个,但是还得加载YUI很不爽,还是自己动手写一个吧~HTML: <!-
- 许可和分发权限Access 2003 Developer Extensions随附的许可协议简化了解决方案或代码段的分发过程。这些协议包括免
- /* --注意:准备数据(可略过,非常耗时) CREATE TABLE CHECK1_T1 ( ID INT, C1 CHAR(8000)
- 今天我们来学习,如何使用有趣的自定义标记来布局页面。有的朋友可能有这样的疑问,自己随便定义的标记浏览器怎么能正确的认识呢?这里我们就要用到文