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 = [　　[1,3,2,6,5,9,8,4,7],
　　[1,2,3,4,5,6,7,8,9],
　　[1,2,3,4,9,6,7,8,5],
　　[2,4,5,1,7,9,6,3,8]
　　]
　　

　　
nums = num_list[0]                   # [1,3,2,6,5,9,8,4,7]
　　
length = len(nums)                    #获取排序的长度
　　for i in range(length):
　　for j in range(length -i -1):       #每比对一遍 找到最大的在最右边
　　if nums[j] > nums[j+1]:         #如果左边的比右边的大
　　tmp = nums[j]                   #暂存这个大的数
　　nums[j] = nums[j+1]        #这个大数的位置换成 右边的较小的数
　　nums[j+1] = tmp              #把大的数放到右边
　　#nums[j],nums[j+1] = nums[j+1],nums[j]     #以上三行可写成一行
　　
print(nums)
　　

　　对以上代码加入统计交换与比对次数
　　实现流程如下:
　　

　　第1次 --> [1,9,8,5,6,7,4,3,2] [1,8,9,5,6,7,4,3,2] [1,8,5,9,6,7,4,3,2] [1,8,5,6,9,7,4,3,2] [1,8,5,6,7,9,4,3,2]
　　[1,8,5,6,7,4,9,3,2] [1,8,5,6,7,4,3,9,2] [1,8,5,6,7,4,3,2,9]   #第一遍时找出最大的数9 放到N-1位即最后一位
　　第2次--> [1,5,8,6,7,4,3,2,9] [1,5,6,8,7,4,3,2,9] [1,5,6,7,8,4,3,2,9] [1,5,6,7,4,8,3,2,9] [1,5,6,7,4,3,8,2,9]
　　[1,5,6,7,4,3,2,8,9]                                           #第二遍时找出最大的8 n-2位 以次类推
　　

　　第3次 --> [1,5,6,7,4,3,2,8,9] [1,5,6,4,7,3,2,8,9] [1,5,6,4,3,7,2,8,9] [1,5,6,4,3,2,7,8,9]
　　第4次 --> [1,5,6,4,3,2,7,8,9] [1,5,4,6,3,2,7,8,9] [1,5,4,3,6,2,7,8,9] [1,5,4,3,2,6,7,8,9]
　　第5次 --> [1,5,4,3,2,6,7,8,9] [1,4,5,3,2,6,7,8,9] [1,4,3,5,2,6,7,8,9] [1,4,3,2,5,6,7,8,9]
　　第6次 --> [1,4,3,2,5,6,7,8,9] [1,3,4,2,5,6,7,8,9] [1,3,2,4,5,6,7,8,9]
　　第7次 --> [1,3,2,4,5,6,7,8,9] [1,2,3,4,5,6,7,8,9]
　　第8次 --> [1,2,3,4,5,6,7,8,9]
　　第9次 --> [1,2,3,4,5,6,7,8,9]
　　

　　2、加入统计
　　参考代码:
　　

num_list = [　　[1,3,2,6,5,9,8,4,7],
　　[1,2,3,4,5,6,7,8,9],
　　[1,2,3,4,9,6,7,8,5],
　　[2,4,5,1,7,9,6,3,8]
　　]
　　
nums = num_list[0]
　　
count = 0                  #定义比对次数
　　
count_swap = 0       #定义交换次数
　　
length = len(nums)
　　

　　
for i in range(length):
　　for j in range(length - i - i):
　　count += 1
　　if nums[j] > nums[j + 1]:
　　tmp = nums[j]
　　nums[j] = nums[j + 1]
　　nums[j + 1] = tmp
　　#nums[j],nums[j+1] = nums[j+1],nums[j]     #以上三行赞同于这一行
　　count_swap += 1
　　Flag = True  # 是否产生交换
　　if not Flag:  # 在没有 产生交换时退出
　　break
　　
print(nums, count_swap, count)
　　

　　

　　打印结果:

　　当我们把一组数换成nums[1] 即[1,2,3,4,5,6,7,8,9] 时
　　结果:

　　我们可以发现即使给出的数已经是排序好的,程序依然需要遍历比对N次,这显然不合理.
　　3、冒泡排序优化
　　由于以上的简单排序,无论一组数怎么的排列(即使已经是按从小到大的正确排列)都需要全部的比对一次,效率低下,因此需要优化 ,即在一轮比对后,下一次没有发生任何交换时,退出,直接打印结果,如:
　　参考代码:
　　

num_list = [　　[1,3,2,6,5,9,8,4,7],
　　[1,2,3,4,5,6,7,8,9],
　　[1,2,3,4,9,6,7,8,5],
　　[2,4,5,1,7,9,6,3,8]
　　]
　　nums = num_list[0]
　　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[j] >nums[j+1]:
　　tmp = nums[j]
　　nums[j] = nums[j+1]
　　nums[j+1] = 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[j]:
　　nums, nums[j] = nums[j], 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[j]:
　　L,L[j] = L[j],L
　　return L
　　

　　以上都是一些典型的数学问题,转变成代码,可见数学和编程是分不开的,至少都讲究逻辑啊,目前只列举这些,后期如果还有我会再更新上来,欢迎大家留言指正!