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安装路径及pip安装的包列表及路径)
- python怎么设计gui界面(详解python做UI界面的方法)
- python numpy矩阵详解(基于Numpy.convolve使用Python实现滑动平均滤波的思路详解)
- python报表可视化(使用Python快速制作可视化报表的方法)
- python多进程与多线程详解(Python线程之定位与销毁的实现)
- python教程列表排序(Python一行代码实现快速排序的方法)
- python使用教程操作(详解python中@的用法)
- python数据表教程(详解Python sys.argv使用方法)
- python排列组合计算方法(Python实现的排列组合、破解密码算法示例)
- python常用的字符串操作方法(Python字符串的常见操作实例小结)
- python如何编写判断正负数程序(Python实现判断一个整数是否为回文数算法示例)
- python用于机器人(python机器人运动范围问题的解答)
- python电脑端微信自动化(python使用wxpy实现微信消息防撤回脚本)
- python获取系统的utc时间(Python的UTC时间转换讲解)
- python中的reload(搞清楚 Python traceback的具体使用方法)
- python中的多线程详解(python多线程抽象编程模型详解)
- 乔欣 古装剧中的高颜值(古装剧中的高颜值)
- 怎么才可以财富自由(如何让自己实现财富自由)
- 为什么越来越多年轻人回农村(为什么越来越多年轻人回农村生活)
- 怎么快速学好英语(怎么快速学好英语初中)
- 中国留学生都是富二代吗()
- 我们现在吃的苹果是哪里来的 原来现代苹果引入中国仅有一百多年(我们现在吃的苹果是哪里来的)
热门推荐
- sql server中的死锁
- 如何用postman做接口测试(基于postman实现http接口测试过程解析)
- vue.js入门教学第15讲(Vue.js 使用AntV X6的示例步骤)
- h5移动端开发app(移动端H5唤起APP的写法实例IOS、android)
- 云服务器建站要多大带宽(云服务器的带宽要多大?能容纳多少人?)
- pythonftp功能介绍(使用Python操作FTP实现上传和下载的方法)
- windows下nginx负载均衡配置(使用nginx配置访问wgcloud的方法)
- apache 配置域名(apache 二级域名解析 window与linux)
- mysql双主状态不一致(MySQL GTID主备不一致的修复方案)
- 云服务器推荐流程(云服务器入门须知的3个技巧)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9