一 、冒泡排序:

冒泡排序:
属于交换排序;
两两比较大小,交换位置,如同水泡大的往上(右)跑;
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 += 1if 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 += 1Flag = 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 = Falsefor i in range(length):Flag = Falsefor j in range(length -i -1):count +=1if nums[j] >nums[j+1]:tmp = nums[j]nums[j] = nums[j+1]nums[j+1] = tmpcount_swap +=1Flag = True           #是否产生交换if not Flag:                 #在没有 产生交换时退出break
print(nums,count_swap,count)以下是另一种写法,可能更好理解:
def bubble_sort(nums):length = len(nums)count = 0swap = 0for i in range(0, length):count +=1for j in range(i + 1, length):if nums[i] > nums[j]:nums[i], nums[j] = nums[j], nums[i]swap +=1return 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*yif a == 10 and b == 32:        #即x+y == 10同时 脚数是32时 成立 print("鸡有:%s,兔有:%s" %(x,y))

打印结果:

三、最大公约数

问题:给出两个整数,求出最大公约数 ,
公约数:是指两个整数的公共约数(能整除被除数的数)中最大的数.
辗转相除法（又称欧几里得算法） 就是一个机械地求最大公约数问题的算法。
分为除法运算和减法运算两种方法.
假设给出两个数12 42求出最大公约数?

这里使用减法运算,除法运算可以自行尝试.
所谓减法运算法,就是在给出的两个数中以大的不断的送去小的数,最终得到的就是两个数的公约数.

参考代码 :

def MaxP(a,b):aa = abb = bwhile a != b:if a >b:a = a -btmp =aelse:b = b -atmp = breturn "%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再乘以2print("第 %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[i] > L[j]:L[i],L[j] = L[j],L[i]return L

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