冒泡法—三个基本算法之一
- 冒泡法
- 属于交换排序
- 两两比较大小，交换位置，如同水泡咕噜咕噜往上冒
- 结果分为升序、降序
- 升序
- n个数从左到右，编号从0开始到n-1,索引0和1的值进行比较，如果索引0的值大，则交换两者位置， 如果索引1的值大，则不变。继续在比较索引1到2的位置，索引1的值大则交换位置，否则不变。一直到索引n-2和索引n-1的值比较完成，到此，第一轮的比较完成。第二轮的比较从索引0比较到索引n-2（因为最右侧n-1的位置已经是最大值了），以此类推，每轮都会减少一个，直至剩下最后2个数比较。
- 降序
- 和升序相反
# 冒泡算法升序排列 a = 0 # 这个可以删除的，因为Python赋值的是指针 swap = 0 count = 0 lst = [1, 2, 9, 6, 3] lst_len = len(lst) for i in range(lst_len): flag = False for j in range(lst_len - i - 1): count += 1 if lst[j] > lst[j + 1]: a = lst[j] # 交换方法一 lst[j] = lst[j + 1] lst[j + 1] = a # lst[j],lst[j+1] = lst[j+1],lst[j] # 交换方法二，原理与方法一一样 swap += 1 flag = True if not flag: break print("排序结果：{}".format(lst)) print("交换次数：{}".format(swap)) print("循环次数：{}".format(count)) # 冒泡算法降序排列 a = 0 # 这个可以删除的，因为Python赋值的是指针 swap = 0 count = 0 lst = [1, 2, 9, 6, 3] lst_len = len(lst) for i in range(lst_len): flag = False for j in range(lst_len - i - 1): count += 1 if lst[j] < lst[j + 1]: a = lst[j] # 交换方法一 lst[j] = lst[j + 1] lst[j + 1] = a # lst[j],lst[j+1] = lst[j+1],lst[j] # 交换方法二，原理与方法一一样 swap += 1 flag = True if not flag: break print("排序结果：{}".format(lst)) print("交换次数：{}".format(swap)) print("循环次数：{}".format(count))- 冒泡法总结
- 冒泡法需要数据一轮轮的比较
- 可以设定一个标记判断此轮是否有数据交换的发生，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序
- 最差的排序情况是，初始顺序于目标顺序完全相反，遍历次数1，….，n-1之和 n(n-1)/2
- 最好的排序情况是：初始顺序于目标顺序相同，遍历次数n-1
- 时间复杂度为：O(n**2)
原文始发于：用Python实现基本算法—-冒泡法
主题测试文章，只做测试使用。发布者：熱鬧獨處，转转请注明出处：http://www.cxybcw.com/11789.html
赞 (0)
打赏 
微信扫一扫 
支付宝扫一扫
微信扫一扫 支付宝扫一扫 OpenCV on ubuntu using Python
« 上一篇 2019年10月20日 pm3:19
Python入门自学最重要、最全标准库Turtle
下一篇 » 2019年10月20日 pm3:20
