python排序的三种方法(Python实现插入排序和选择排序的方法)
类别:脚本大全 浏览量:2648
时间:2021-10-03 01:40:08 python排序的三种方法
Python实现插入排序和选择排序的方法话不多说,让我们从最基本的排序算法开始吧
插入排序
如下图所示,插入排序的实现思路顾名思义,就是 不断地在一个已经是有序的数组中,寻找合适位置并插入新元素 。
具体实现步骤为:
首先我们把整个数组拆分为有序区间和未排序区间,有序区间在插入排序一开始只有一个元素,就是数组的第一个元素。
接在有序区间之后的一个元素就是准备插入的元素,在图中就是标为绿色的元素,在有序区间内寻找位置并插入。
其寻找逻辑为:从后往前依次进行比较,如果待插入元素大于当前元素,则将待插入元素插入到当前元素的后一位,如果待插入元素小于当前元素,则将当前元素后移一位。不断重复该过程直至到数组的最后一位
其实现的具体代码为:
|
def insertion_sort(a): length = len (a) if length < = 1 : return for i in range ( 1 ,length): j = i - 1 value = a[i] while j > = 0 : if a[j]<value: a[j + 1 ] = value break else : a[j + 1 ] = a[j] if j = = 0 : a[j] = value j - = 1 print (a) |
return a时间复杂计算为:我们需要将整个数组遍历一遍,所以这一部分为o(n),在每一次遍历中都要执行一次插入操作,其时间复杂度为o(n),所以总时间复杂度为o(n2)
选择排序
选择排序跟插入排序算法类似,都是将数组分为有序区间和未排序区间,区别在于插入排序是将一个新元素插入到有序区间内,而选择排序则是在未排序区间中找到最小元素,并交换到有序区间之后。
实现代码为:
|
def selection_sort(a): length = len (a) if length < = 1 : return for i in range ( 0 ,length - 1 ): min_value = a[i] min_index = i j = i + 1 while j<length: if a[j] < min_value: min_value = a[j] min_index = j j + = 1 a[i],a[min_index] = a[min_index],a[i] |
return a时间复杂度计算:数组长度为n,一共需要寻找n次最小值,每次寻找最小值都要遍历未排序区间一次,其时间复杂度为o(n),乘以n次为o(n2)
原文链接:https://segmentfault.com/a/1190000019151804
您可能感兴趣
- python如何判断两个数组相同(Python实现的合并两个有序数组算法示例)
- 用mysql语句写python学生管理系统(Python基于mysql实现学生管理系统)
- python气温变化数据分析(基于python历史天气采集的分析)
- python中如何清空列表数据(Python批量删除只保留最近几天table的代码实例)
- python3有哪些内置模块(Python3.5内置模块之os模块、sys模块、shutil模块用法实例分析)
- python调用excel教程(利用python在excel里面直接使用sql函数的方法)
- python ssh 连接(python pexpect ssh 远程登录服务器的方法)
- python坐标输入(python导入坐标点的具体操作)
- 抖音上很火的表白程序链接(我喜欢你 抖音表白程序python版)
- python 微信二维码接口(python实现微信防撤回神器)
- opencv 图像匹配python(OpenCV+Python识别车牌和字符分割的实现)
- python获取日期(Python根据当前日期取去年同星期日期)
- python把str转成list(python3 字符串/列表/元组str/list/tuple相互转换方法及join函数的使用)
- python开启两个线程(Python开启线程,在函数中开线程的实例)
- python读取和写入数据excel(Python向excel中写入数据的方法)
- python包和模块管理(python的依赖管理的实现)
- 写信告诉我今天海是什么颜色(写信告诉我今天海是什么颜色回答)
- 英语难学吗(法语比英语难学吗)
- 今天要吃什么(今天要吃什么菜好)
- 网红直播可以赚很多钱吗(网红直播可以赚很多钱吗)
- 今天是什么日子(今天是什么日子有什么特殊意义吗)
- 这里输入关键词(怎么输入关键词搜索)
热门推荐
- php如何调用类(php创建类并调用的实例方法)
- sqlserver实现登录注册(Sqlserver创建用户并授权的实现步骤)
- ASP.NET常用加密解密方法
- mybatis 一对多条件查询(mybatis collection 多条件查询的实现方法)
- python dict 操作(Python中dict和set的用法讲解)
- dedecms操作(织梦DedeCMS官方关于正版版本号的严正声明)
- 解释mysql慢查询(MySQL Threads_running飙升与慢查询的相关问题解决)
- 如何在webpack中搭建项目(如何在webpack项目中调试loader插件)
- mysql查看慢查询(MySQL 慢查询日志深入理解)
- dedecms屏蔽规则(织梦dedecms修改任意管理员漏洞处理方法)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9