Python算法100例-1.8 冒泡排序

完整源代码项目地址,关注博主私信’源代码’后可获取

  • 1.问题描述
  • 2.问题分析
  • 3.算法设计
  • 4.完整的程序
  • 5.问题拓展

1.问题描述

对N个整数(数据由键盘输入)进行升序排列。

2.问题分析

对于N个类型相同的数,我们可利用数组进行存储。冒泡排序是利用两个相邻元素之间进行比较交换的过程将一个无序表变成有序表。

冒泡排序的思想是:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小。若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,称之为消去了一个逆序。在扫描过程中,不断地将两相邻元素中的大者往后移动,最后就将数组中的最大者换到了表的最后,这正是数组中最大元素应有的位置。然后,在剩下的数组元素中(n-1个元素)重复上面的过程,将次小元素放到倒数第2个位置。不断重复上述过程,直到剩下的数组元素为0为止,此时的数组就变为了有序。假设数组元素的个数为n,在最坏的情况下需要的比较总次数为:((n-1)+(n-2)+…+2+1)=n(n-1)/2。

3.算法设计

冒泡排序的过程我们可以用示意图简单地表示,如图所示。从整个排序过程中寻找规律,可知n个元素只需比较n-1次即可。假设一个数组中有7个元素,现在对这7个元素进行排序,只需比较6次即可得到所要的有序序列。示意图中最后加粗的数字即为经过一次交换位置固定的数字。

在这里插入图片描述

数组名用a表示,数组下标用j表示,则数组中相邻两个元素的下标可表示为a[j]、a[j+1]或a[j-1]、a[j]。在利用数组解决问题时需要注意数组下标不要越界,假如定义一个整形数组int a[n],则数组元素下标的取值范围是0~n-1,下标小于0或者大于n-1都视为下标越界。如果相邻元素采用a[j]、a[j+1]表示,则下标取值范围是0~n-2,如果采用a[j-1]、a[j]表示,下标取值范围则是1~n-1,所以读者在进行编程时一定要注数组下标越界的问题。

数组元素互换也是经常遇到的一类题型,一般这种情况下我们需要借助一个中间变量才可以完成,对于许多初学者来说经常犯的一个错误是对两个元素直接相互赋值,而不借助中间变量。我们先来看一个生活中的例子,在蓝墨水瓶中装有蓝墨水,红墨水瓶中装有红墨水,现在我们要把蓝墨水放到红墨水瓶中,红墨水放到蓝墨水瓶中。做法是先找一个白色空瓶(作用相当于程序中的中间变量),首先将蓝墨水倒入白色空瓶(t=a[i]或t=a[i+1]),接着将红墨水倒入蓝墨水瓶(a[i]=a[i+1]或a[i+1]=a[i]),最后将白瓶中的蓝墨水倒入红墨水瓶(a[i+1]=t或a[i]=t),经过这三步就完成了红墨水与蓝墨水的互换。如果不借助白色空瓶,直接把蓝墨水倒入红墨水瓶或把红墨水倒入蓝墨水瓶,这样必将破坏原来所存储的内容。第一次的交换过程可以用简单的程序段进行表示,代码如下:

for j in range(0, n-1):if a[j] > a[j+1]:t = a[j]                                    # 使用变量t暂存a[j] = a[j+1]a[j+1] = t

第二次的交换过程(最后一个元素经过第一轮比较已经确定,不需要再次进行比较)可表示为:

for j in range(0, n-2):if a[j] > a[j+1]:t = a[j]                                    # 使用变量t暂存a[j] = a[j + 1]a[j + 1] = t

第三次的交换过程(最后两个元素已经确定,不需要再次进行比较)可表示为:

for j in range(0, n-3):if a[j] > a[j+1]:t = a[j]                                    # 使用变量t暂存a[j] = a[j + 1]a[j + 1] = t

由上面的程序段可以发现,第一次比较的判定条件为j<n-1,第二次为j<n-2,第三次为j<n-3,以此类推,第i次的循环判定条件必为j<n-i。在编程过程中我们可以用两层循环来控制,第一层循环控制交换的轮数,第二层循环控制每轮需要交换的次数。

4.完整的程序

程序流程图如图所示。

在这里插入图片描述

根据上面的分析,编写程序如下:

%%time
# 冒泡排序
def bubbleSort(a):# 首先获取列表list的总长度,为之后循环比较做准备n = len(a)# 进行 n-1 次比较,控制比较的轮数i = 1while i <= n-1:# 控制每轮比较的次数j = 0while j < n-i:# 交换if a[j] > a[j+1]:t = a[j]a[j] = a[j+1]a[j+1] = tj += 1i += 1# 打印每一轮交换后的列表for a1 in a:print(a1, end=" ")if __name__=="__main__":print("请为列表元素赋初值,列表末尾不能有空格:")x = input()a = x.split(" ")                                        # 以空格方式分割每个元素for i in range(0, len(a)):              # 输入多个值a[i] = int(a[i])print("你输入的列表元素为:\n", a)print("经过交换后的数组元素为:")bubbleSort(a)
请为列表元素赋初值,列表末尾不能有空格:
你输入的列表元素为:[5, 7, 9, 8, 2, 3, 1, 6, 4]
经过交换后的数组元素为:
1 2 3 4 5 6 7 8 9 CPU times: user 195 ms, sys: 53.3 ms, total: 248 ms
Wall time: 24.6 s

5.问题拓展

常用的排序方法除了上述的冒泡法外,还有选择排序、插入排序、快速排序、堆排序等,下面简单介绍选择排序。

选择排序的思想是:扫描整个线性表,第一轮比较拿数组中的第一个元素与其他元素进行比较,遇到比第一个元素小的元素则进行交换,再拿着交换之后的第一个元素接着从上次比较的位置与后面的元素进行比较,直到扫描到线性表的最后,从中选出最小的元素,将它交换到表的最前面(这是它应有的位置);第二轮比较的时候从第二个元素开始,依次与第三个、第四个直到最后一个进行比较,在比较过程中有比第二个元素小的元素则进行交换,接着与后面的元素比较;对剩下的子表采用同样的方法,直到子表为空。在最坏的情况下,需要比较n(n-1)/2次。

完整的程序如下:

%%time
# 选择排序
def selectionSort(a):# 求出列表的长度n = len(a)for i in range(0, n-1):for j in range(i+1, n):#交换if a[j] < a[i]:t = a[i]a[i] = a[j]a[j] = tfor i in a:print(i, end=" ")if __name__=="__main__":print("请为列表元素赋初值,列表末尾不能有空格:")x = input()a = x.split(" ")                                        # 以空格方式分割每个元素for i in range(0, len(a)):              # 输入多个值a[i] = int(a[i])print("你输入的列表元素为:\n", a)print("经过交换后的数组元素为:")selectionSort(a)print("\n")
请为列表元素赋初值,列表末尾不能有空格:
你输入的列表元素为:[5, 7, 9, 8, 2, 3, 1, 6, 4]
经过交换后的数组元素为:
1 2 3 4 5 6 7 8 9 CPU times: user 124 ms, sys: 35.4 ms, total: 159 ms
Wall time: 15.5 s

不同排序法的效率是不同的,不同需求情况下可选择不同的方法。其他几种排序方法的原理有兴趣的读者可参阅数据结构的相关内容。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/260433.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QT-地形3D

QT-地形3D 一、 演示效果二、关键程序三、下载链接 一、 演示效果 二、关键程序 #include "ShaderProgram.h"namespace t3d::core {void ShaderProgram::init() {initializeOpenGLFunctions();loadShaders(); }void ShaderProgram::addShader(const QString &fil…

2、windows环境下vscode开发c/c++环境配置(一)

前言&#xff1a;VSCode是微软出的一款轻量级编辑器&#xff0c;它本身只是一款文本编辑器而已&#xff0c;并不是一个集成开发环境(IDE)&#xff0c;几乎所有功能都是以插件扩展的形式所存在的。因此&#xff0c;我们想用它编程&#xff0c;不只是把vscode下载下来就行&#x…

面试redis篇-03缓存击穿

原理 缓存击穿:给某一个key设置了过期时间,当key过期的时候,恰好这时间点对这个key有大量的并发请求过来,这些并发的请求可能会瞬间把DB压垮 解决方案一:互斥锁 解决方案二:逻辑过期 提问与回答 面试官 :什么是缓存击穿 ? 怎么解决 ? 回答: 缓存击穿的意思…

桌面便签怎么设置提醒,哪个备忘录便签好?

2024年终于开工了&#xff0c;第一天上班比较迷茫&#xff0c;不知道做什么比较好&#xff0c;这个时候如果有一款简单好用且可提醒的桌面便签软件该多好。那么&#xff0c;桌面便签怎么设置提醒&#xff0c;哪个备忘录便签好&#xff1f; 桌面便签怎么设置提醒&#xff0c;哪个…

2024-02-19(Flume,DataX)

1.flume中拦截器的作用&#xff1a;个人认为就是修改或者删除事件中的信息&#xff08;处理一下事件&#xff09;。 2.一些拦截器 Host Interceptor&#xff0c;Timestamp Interceptor&#xff0c;Static Interceptor&#xff0c;UUID Interceptor&#xff0c;Search and Rep…

力扣145 二叉树的后序遍历 Java版本

文章目录 题目描述递归解法代码 非递归解法思路代码 题目描述 给你一棵二叉树的根节点 root &#xff0c;返回其节点值的 后序遍历 。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[3,2,1] 示例 2&#xff1a; 输入&#xff1a;root [] 输出…

NX/UG二次开发—CAM—平面铣边界准确设置方法

大家在对平面铣设置边界时&#xff0c;经常遇到边界方向与自己期望的不一致&#xff0c;有些人喜欢用检查刀路是否过切来判断&#xff0c;但是对于倒角、负余量等一些情况&#xff0c;刀路本来就是过切的。对于多边界&#xff0c;可以根据选择的曲线来起点和面的方向来确定&…

大数据信用报告查询方式一般有几种?哪种比较好?

在了解这个问题之前&#xff0c;想必你对大数据信用与人行信用的区别都是比较清楚了&#xff0c;本文呢就着重讲一下大数据信用报告查询方式有几种&#xff0c;哪种比较好&#xff0c;感兴趣的朋友不妨一起去看看。 大数据信用报告常见的三种查询方式&#xff1a; 一、二维码分…

正则表达式与正则可视化工具:解密文本处理的利器

正则表达式与正则可视化工具&#xff1a;解密文本处理的利器 引言 在计算机科学和软件开发领域&#xff0c;正则表达式是一种强大而灵活的文本处理工具。然而&#xff0c;对于初学者来说&#xff0c;正则表达式的语法和规则可能会显得晦涩难懂。为了帮助初学者更好地理解和学…

Linux系统之iptables应用SNAT与DNAT

一、SNAT&#xff1a; 1.应用环境 局域网主机共享单个公网IP地址接入Internet &#xff08;私有IP不能在Internet中正常路由&#xff09; 2.SNAT原理 源地址转换&#xff0c;根据指定条件修改数据包的源IP地址&#xff0c;通常被叫做源映谢数据包从内网发送到公网时&#x…

Qt:自定义信号,信号emit,传参问题,信号槽与moc

一、自定义信号&#xff0c;信号emit 1、自定义信号 在头文件中 加入signals&#xff1a; 就可以编写信号 2、emit emit的作用是通知信号发生 二、跨UI控件传参 每次按Dialog添加按钮主控件数字会增长 // .h private slots:void on_btnAdd_clicked(); signals:void sign…

基于Springboot+Vue实现的宿舍管理系统

基于SpringbootVue的宿舍管理系统 1.系统相关性介绍1.1 系统架构1.2 设计思路 2.功能模块介绍2.1 用户信息模块2.2 宿舍管理模块2.3 信息管理模块 3. 源码获取以及远程部署 前言&#xff1a; 在现代教育环境中&#xff0c;学生宿舍的管理显得尤为重要&#xff0c;需要一套能…

OpenCV边缘检测与视频读写

原理 OpenCV中的边缘检测原理主要基于图像梯度的计算&#xff0c;包括一阶梯度和二阶梯度。 一阶梯度&#xff1a;它反映了图像亮度变化的速度。Sobel算法就是一种以一阶梯度为基础的边缘检测算法。它通过计算图像在水平和垂直方向上的梯度来检测边缘。这种方法简单有效&…

领域驱动设计(Domain Driven Design)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、场景和要求二、领域模型关键词1.领域2.子域3.通用语言4.限界上下文5.领域模型6.实体和值对象7.聚合根8.领域服务9.领域事件 总结 前言 Domain Driven Desi…

环信IM Android端实现华为推送详细步骤

首先我们要参照华为的官网去完成 &#xff0c;以下两个配置都是华为文档为我们提供的 1.https://developer.huawei.com/consumer/cn/doc/HMSCore-Guides/android-config-agc-0000001050170137#section19884105518498 2.https://developer.huawei.com/consumer/cn/doc/HMSCore…

JAVA高并发——人手一支笔:ThreadLocal

文章目录 1、ThreadLocal的简单使用2、ThreadLocal的实现原理3、对性能有何帮助4、线程私有的随机数发生器ThreadLocalRandom4.1、反射的高效替代方案4.2、随机数种子4.3、探针Probe的作用 除了控制资源的访问&#xff0c;我们还可以通过增加资源来保证所有对象的线程安全。比如…

继续教育公需科目试题及答案,分享几个实用搜题和学习工具 #经验分享#经验分享

大学生活是一个充满挑战和机遇的阶段&#xff0c;在这个阶段&#xff0c;我们需要不断提升自己的学习能力和技巧。而寻找适合自己的学习工具也成为了我们必须面对的任务。幸运的是&#xff0c;现在有许多日常学习工具可以帮助我们更好地组织学习、提高效率。今天&#xff0c;我…

SQL Developer 小贴士:显示Trace文件

SQL Developer可以识别trace文件&#xff0c;而无需利用tkprof进行转换。 在数据库服务器上生产trace文件。例如&#xff1a; alter session set tracefile_identifierdemo01_02;alter session set sql_tracetrue;-- your SQL here, for example select * from hr.employees;a…

什么是渲染?渲染有几种类型?渲染100邀请码1a12

渲染是CG作业的最后一步&#xff0c;根据分类依据不同&#xff0c;有以下几个类型&#xff1a; 1、操作响应 根据对渲染结果的响应要求和实现原理不同&#xff0c;渲染可分为离线渲染、实时渲染和混合渲染。离线渲染通常在本地进行&#xff0c;由电脑生成画面&#xff0c;时间从…

TimeDad 简单的PC使用时间控制软件

TimeDad 起因 过年教家里的小朋友玩我的世界&#xff0c;这家伙着了魔&#xff0c;每天霸着电脑&#xff0c;说梦话都是挖矿。 找了time boss破解版用了一段时间&#xff0c;破解失效了。找了一圈软件发现功能都好复杂&#xff0c;要收费的&#xff0c;没办法&#xff0c;娃…