1. 首页
  2. Python

用Python实现基本算法—-冒泡法

冒泡法—三个基本算法之一

  • 冒泡法
    • 属于交换排序
    • 两两比较大小,交换位置,如同水泡咕噜咕噜往上冒
    • 结果分为升序、降序

  • 升序
    • 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

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code