python冒泡排序与常用数学计算
一 、冒泡排序:冒泡排序:
属于交换排序;
两两比较大小,交换位置,如同水泡大的往上(右)跑;
n个数从左至右编号从0到n-1,索引0和1比较,如果索引0大,则交换两者位置;
如果索引1大则不用交换继续比较索引1和2的值,将大值放在右侧,直到n-2和n-1
比较完,第一轮比较完成,第二轮从索引0比较到n-2,因为最右侧n-1位置上已经是
最大值了,依次类推,第一轮都会减少最右侧的不参与比较,直到剩下最后2个数比较.
以上定义在任何编程语言中都是同样的实现逻辑,以下在python中实现.
1、冒泡简单实现
参考代码
num_list = [ ,
,
,
]
nums = num_list #
length = len(nums) #获取排序的长度
for i in range(length):
for j in range(length -i -1): #每比对一遍 找到最大的在最右边
if nums > nums: #如果左边的比右边的大
tmp = nums #暂存这个大的数
nums = nums #这个大数的位置换成 右边的较小的数
nums = tmp #把大的数放到右边
#nums,nums = nums,nums #以上三行可写成一行
print(nums)
对以上代码加入统计交换与比对次数
实现流程如下:
第1次 -->
#第一遍时找出最大的数9 放到N-1位即最后一位
第2次-->
#第二遍时找出最大的8 n-2位 以次类推
第3次 -->
第4次 -->
第5次 -->
第6次 -->
第7次 -->
第8次 -->
第9次 -->
2、加入统计
参考代码:
num_list = [ ,
,
,
]
nums = num_list
count = 0 #定义比对次数
count_swap = 0 #定义交换次数
length = len(nums)
for i in range(length):
for j in range(length - i - i):
count += 1
if nums > nums:
tmp = nums
nums = nums
nums = tmp
#nums,nums = nums,nums #以上三行赞同于这一行
count_swap += 1
Flag = True# 是否产生交换
if not Flag:# 在没有 产生交换时退出
break
print(nums, count_swap, count)
打印结果:
当我们把一组数换成nums 即 时
结果:
我们可以发现即使给出的数已经是排序好的,程序依然需要遍历比对N次,这显然不合理.
3、冒泡排序优化
由于以上的简单排序,无论一组数怎么的排列(即使已经是按从小到大的正确排列)都需要全部的比对一次,效率低下,因此需要优化 ,即在一轮比对后,下一次没有发生任何交换时,退出,直接打印结果,如:
参考代码:
num_list = [ ,
,
,
]
nums = num_list
count = 0 #定义比对次数
count_swap = 0 #定义交换次数
length = len(nums)
Flag = False
for i in range(length):
Flag = False
for j in range(length -i -1):
count +=1
if nums >nums:
tmp = nums
nums = nums
nums = tmp
count_swap +=1
Flag = True #是否产生交换
if not Flag: #在没有 产生交换时退出
break
print(nums,count_swap,count)
以下是另一种写法,可能更好理解:
def bubble_sort(nums):
length = len(nums)
count = 0
swap = 0
for i in range(0, length):
count +=1
for j in range(i + 1, length):
if nums > nums:
nums, nums = nums, nums
swap +=1
return nums,count,swap
print(bubble_sort(nums))
结果如下:
很明显 这次交换数为0,即没有 发生交换,遍历比对数是8,大大提高了效率
4、冒泡总结:
冒泡法需要数据一轮轮的比较;
可以设定一个标记判断此轮是否有数据交换发生,如果没有发生交换,可以结束排序,如果发生交换继续下一轮排序
最差的排序情况是初始顺序与目标顺序完全相反,遍历次数1...n-1之和n(n-1)/2
最好的排序情况:初始顺序与目标顺序相同,遍历次数n-1
时间复杂度O(n^2)
二、鸡兔同笼问题(二元一次方程)
问题:
一只笼子里有鸡和兔子共计10只把它们的脚加起来共计32只,问鸡和兔子各有多少只?
思路:我们可以用初中的二次一次方程来解,即:
设鸡x,兔为y则
x + y = 10
2x +4y = 32
以上只不过是我们初中学到的二元一次方程而已,
参考代码 :
for x in range(10): #因为鸡在10以内 for y in range(10): #兔子也在10以内
a = x + y #类似试着尝试
b = 2*x + 4*y
if a == 10 and b == 32: #即x+y == 10同时 脚数是32时 成立
print("鸡有:%s,兔有:%s" %(x,y))
打印结果:
三、最大公约数
问题:给出两个整数,求出最大公约数 ,
公约数:是指两个整数的公共约数(能整除被除数的数)中最大的数.
辗转相除法（又称欧几里得算法） 就是一个机械地求最大公约数问题的算法。
分为除法运算和减法运算两种方法.
假设给出两个数12 42求出最大公约数?
这里使用减法运算,除法运算可以自行尝试.
所谓减法运算法,就是在给出的两个数中以大的不断的送去小的数,最终得到的就是两个数的公约数.
参考代码 :
def MaxP(a,b): aa = a
bb = b
while a != b:
if a >b:
a = a -b
tmp =a
else:
b = b -a
tmp = b
return "%s和%s最大公约数%s" %(aa,bb,tmp)
运行结果:
注意1是所有数的公约数!
四、判断一个数是否为素数
素数:不能被任何比它自身小的整数而整除的数(除1和自身)
问题:给定一个数判断它是否是一个素数,通过定义我们来写出程序.
参考代码 :
def IsS(x): for i in range(2,x):
if x % i == 0:
return ("%s is not 素数!" %x)
return ("%s is 素数!" %x)
print(isS(99991))
运行结果:
五、猴子吃桃问题
问题:
猴子摘取了一些桃子,当即吃了一半又多吃了一个,第二又吃了剩下的一半,又多吃一个,依次吃法,每天吃前一天的一半再多吃一个,第十天时猴子发现就剩下一个桃子了,请问当初猴子一共摘了多少桃子 ?
分析:
此题是小学奥数题,倒着往前推,第10天还没有吃就只剩下1个桃子,假设第九天还有x个桃子 ,那么第十天就是:x %2 -1 =1,算出 第九天有四个桃子,以此类推即可.
参考代码:
num =1 #第10天还没有吃呢就剩下 1
print("第10天还没有吃呢就剩下 1 个桃子了!")
for day in range(9,0,-1): #倒推从第九天开始算#
num = (num+1) *2 #现在 剩下的就是前一天加1再乘以2
print("第 %d 天还有 %d 个桃子!" %(day,num))
运行结果:
留下 一个思考题目:
现有一个已经排好序的数组,现在需要往里插入一个数,要求被插入的数需要按原来的规律插入.
参考代码:
def Ssort(L,a): L.append(a)
length = len(L)
for i in range(length):
for j in range(i+1,length):
if L > L:
L,L = L,L
return L
以上都是一些典型的数学问题,转变成代码,可见数学和编程是分不开的,至少都讲究逻辑啊,目前只列举这些,后期如果还有我会再更新上来,欢迎大家留言指正!
页:
[1]