Python3冒泡排序
2024-09-06 06:07:33
练习:将路径为 D:\data.txt 的文件读取,并取出数字部分进行排序(不能使用内置排序方法),这里我们使用冒泡排序法
文件读取并取出数字部分(略)
一:什么叫冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,一层一层的将较大的元素往后移动,其现象和气泡在上升过程中慢慢变大类似,故成为冒泡排序。
1:原理
- 从第一个和第二个开始比较,如果第一个比第二个大,则交换位置,然后比较第二个和第三个,逐渐往后
经过第一轮后最大的元素已经排在最后,所以重复上述操作的话第二大的则会排在倒数第二的位置。
那重复上述操作n-1次即可完成排序,因为最后一次只有一个元素所以不需要比较
with open('D:\data.txt','r+') as f:
res = f.read()
print(res) #字符串替换,将空格替换为逗号
res = res.replace('\n',',')
print('res为:',res) #字符串分割,将字符串以逗号分隔成为一个列表
m = res.split(',')
print('m为:',m) #取出数字部分
li = []
for i in m:
if i.isdigit():
li.append(i)
#冒泡排序
cd = len(li)
while cd > 0:
for i in range(len(li)-1):
if li[i] > li[i+1]:
li[i],li[i+1] = li[i+1],li[i] #交换列表元素,相当于一次性赋了两个值
cd -=1
print(li)
2:特性
冒泡排序是一种简单直接暴力的排序算法,为什么说它暴力?因为每一轮比较可能多个元素移动位置,而元素位置的互换是需要消耗资源的,所以这是一种偏慢的排序算法,仅适用于对于含有较少元素的数列进行排序。
- 稳定性:我们从代码中可以看出只有前一个元素大于后一个元素才可能交换位置,所以相同元素的相对顺序不可能改变,所以它是稳定排序
比较性:因为排序时元素之间需要比较,所以是比较排序
时间复杂度:因为它需要双层循环n*(n-1)),所以平均时间复杂度为O(n^2)
空间复杂度:只需要常数个辅助单元,所以空间复杂度为O(1),我们把空间复杂度为O(1)的排序成为原地排序(in-place)
记忆方法:想象成气泡,一层一层的往上变大
最新文章
- Linux线程体传递参数的方法详解
- Daily Scrum Meeting ——NinthDay
- Poj 3250 单调栈
- Gliffy
- 图解TCP/IP读书笔记(三)
- [转]前景检测算法--ViBe算法
- java设计模式---原型模式
- hibernate4 spring3.2 事务不提交分析
- seo步骤
- Extjs4中的布局
- nginx安装文档
- js代码执行顺序问题
- MTLAB: 稀疏矩阵的表示-sparse
- webapi 统一处理时间格式
- 指数型生成函数(EGF)学习笔记
- django之 使用views.py里面的函数对表进行增删改查 内容(models.py中表的创建、views.py中函数的使用,基于对象的跨表查询)
- NYOJ 737:石子合并(一)(区间dp)
- 第三章 消息摘要算法--MD5
- php 非常简单的导入sql文件
- 触发器五(建立INSTEAD OF触发器)(学习笔记)
热门文章
- Spring Boot 2.3.0 新特性Redis 拓扑动态感应
- String a=new String(";abc";)创建了几个对象
- DDD实践反思
- Python学习笔记-PuLP库(3)线性规划实例
- 1079 Total Sales of Supply Chain
- 991. Broken Calculator
- .NET 中的 Worker Service 入门介绍
- deep freeze standard v8.x
- POJ2118基础矩阵快速幂
- CVE-2011-0104:Microsoft Office Excel 中的栈溢出漏洞调试分析