冒泡法—三个基本算法之一
- 冒泡法
- 属于交换排序
- 两两比较大小,交换位置,如同水泡咕噜咕噜往上冒
- 结果分为升序、降序
- 升序
- 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