Python | 有趣的冒泡排序
发布于2021-06-07 21:10 阅读(1430) 评论(0) 点赞(1) 收藏(3)
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。
引言
喝汽水的时候，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。而我们的冒泡排序之所以叫做冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。
解决方案
冒泡排序逻辑比较简单，易于理解。
步骤大致如下：对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。如果从小到大排序，这时，较小的数据就会逐个向前移动，好像气泡向上漂浮一样。生活中，我们在集体活动中站队时，第一次站队由于没有固定的位置，往往是大家先随便站成一排，然后再通过换位置的方式逐步形成高矮顺序，这就体现了冒泡排序的思想
下面用画图来表示一下该过程：
通过观察我们不难发现，第一轮比较了4次，第二轮比较了3次，第三轮比较了2次，第四轮比较了1次。为什么每一轮相互比较的次数都减少了一次？因为在第一轮比较结束的时候，这一组数据中最大的数23已经下沉到最底，之后的每一轮比较的时候都不用再去比较23；第二轮比较结束的时候，次大的12也沉到了倒数第二的位置，跟23一样，在之后的每一轮比较中就不用再去比较12了。第三轮结束和第四轮结束的情况也是类似。
由此我们可以发现冒泡排序的特点：冒泡排序把N个数通过N-1轮排序，升序排序时每一轮比较会把最大的数下沉到最底(降序排序则反之)，所以相互比较的次数每一轮都会比前一轮少一次。
下面我们用Python代码实现该算法：
List = [] lenth = len(List) for i in range(0,lenth): for j in range(i+1,lenth): if List[j] < List[i]: List[i] , List[j] = List[j] , List[i] #升序用>,降序用< return List |
实际使用该算法时我们会发现这样一个问题：由于每次比较没有记录，即使是一个完全有序的含有N个数的序列，程序也会运行N-1次。
为了改善这种情况，我们可以通过标记flag来优化排序，当在双重循环还未循环完毕的时候，如果已经完成了排序，则通过标记flag达到结束的效果。
代码如下：
List = [] lenth = len(List) for i in range(0,lenth): flag = 0 for j in range(i+1,lenth): if List[j] < List[i]: List[i] , List[j] = List[j] , List[i] #升序用>,降序用< flag += 1 if flag == 0: break |
结语
本文简单介绍了一下冒泡排序的原理及优化方法。虽然该算法效率不高，但是每个算法都有合适的应用场景。
实习编辑：李欣容
稿件来源：深度学习与文旅应用实验室（DLETA）
原文链接:https://blog.csdn.net/gschen_cn/article/details/117608586
所属网站分类: 技术文章 > 博客
作者：T4yufbhhhh
链接：http://www.phpheidong.com/blog/article/89530/8aeae1238a2a2286e055/
来源：php黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力