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


猜你喜欢
- 暂时是一个手动设置无向图中的边,用一个二维数组表示,后面会改进为用户自己定义无向图的边。学习python的新手,若大佬有解决的办法,希望不吝
- 前言我们知道当文件不存在的时候,open()方法的写模式与追加模式都会新建文件,但是对文件进行判断的场景还有很多,比如,在爬虫下载图片的时候
- 1.检查mysql是否安装yum list installed | grep mysql如果有的话 就全部卸载yum -y remove +
- pip install命令默认是用的是python官方源,由于一些客观原因,连接速度很慢,甚至超时中断,到时很多模块安装不上,甚是苦恼!怎么
- 如何用拦截表单的方法上传图片? 看下列代码:<script language="
- 采用python实现简单QQ单用户机器人的方法如下:一、首先我们查看一下关于3GQQ的相关协议: 对此,
- 内容摘要:本文介绍了使用CSS结合javascript来实现对超链接的类型进行标注,让浏览者明确是zip,doc,pdf或其它格式的文件。这
- 如下所示:# -*- coding: utf-8 -*-import os import pandas as pdimport numpy
- 本文实例讲述了PHP使用Face++接口开发微信公众平台人脸识别系统的方法。分享给大家供大家参考。具体如下:效果图如下:具体步骤如下:首先,
- keys()方法返回在字典中的所有可用的键的列表。语法以下是keys()方法的语法:dict.keys()参数 &nb
- 需求:web系统有包含以下5个url,分别对于不同资源;1、stu/add_stu/2、stu/upload_homework/3、stu/
- 听歌识曲,顾名思义,用设备“听”歌曲,然后它要告诉你这是首什么歌。而且十之八九它还得把这首歌给你播放出来。这样的功能在QQ音乐等应用上早就出
- 本程序有两文件test.asp 和tree.asp 还有一些图标文件 1。test.asp 调用类生成树 代码如下<%@
- 阅读上一篇:网马解密大讲堂——网马解密初级篇今天主要讲解的内容是Freshow工具的使用方法,工欲善其事,必先利其器,首先要学会如何使用解密
- 1.简介keplergl是由Uber开源的一款地理数据可视化工具,通过keplergl我们可以在Jupyter notebook中使用,可视
- defer用于资源的释放,会在函数返回之前进行调用。如果有多个defer表达式,调用顺序类似于栈,越后面的defer表达式越先被调用。def
- 本文实例为大家分享了一组典型数据格式转换的python实现代码,供大家参考,具体内容如下有一组源数据,第一行会是个日期数据,第二行标明字段,
- psutil是个跨平台库,能够轻松实现获取系统运行的进程和系统利用率,包括CPU、内存、磁盘、网络等信息。它主要应用于信息监控,分析和限制系
- 网上关于javascript实现数字时钟效果的实例很多,但是本文给大家介绍的是滚动效果的数字时钟。小编觉得效果很炫,下面分享给大家。先来看看
- 图片外框特征参数:①dashed:虚线 ②dotted:点虚线 ③solid:实线 ④double:双线 ⑤groove:沟槽状 ⑥ridg