Python 如何优化冒泡排序
Python 如何优化冒泡排序
JavaFish
发布于 2019-10-17 17:14:11
发布于 2019-10-17 17:14:11
什么叫冒泡排序法？
相信有接触过算法的朋友多少都了解冒泡排序法，那么什么是冒泡排序法呢？冒泡排序，英文名称（Bubble Sort）是一种基础的交换排序算法，在日常工作中经常会用到，例如：页面数据需按时间先后排序，这本质上也是一种冒泡排序法。
喝过可乐的朋友都知道，可乐里面的气泡会向上浮，这就是冒泡排序一种最形象的例子。至于有些朋友问，是大的气泡先上浮还是小的先上浮呢？这就取决于你的需求去做控制了。
先上动图，再结合代码介绍一下冒泡排序算法的执行过程。
冒泡排序.gif
基础版
def bubble_sort(list):
x = len(list)
# 这个循环负责设置冒泡排序进行的次数
for i in range(x - 1):
# 这个循环负责控制比较的元素个数
for j in range(0, x - 1 - i):
# 交换顺序
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j +1], list[j]
return list
list = [3,1,2,4,5]
print(bubble_sort(list)) 由 gif 图结合代码可以看出，就算当前数列中的某几个元素之间是有序的(数列最后两个元素 4 和 5 是不应该比较的)，元素遍历依然会执行，但这种操作是毫无意义的。这明显会导致效率低下，以及资源消耗。在这种情况下冒泡排序算法的时间复杂度是 O(N^2)
鉴于基础版冒泡排序效率低下，改进版应运而生。
改进版
在基础版中已经知道就算当前数列中的某几个元素之间是有序的(如最后的4、5)，元素遍历依然会执行。而我们改进版就是为了解决这个问题。
def bubble_sort(list):
x = len(list)
# 这个循环负责设置冒泡排序进行的次数
for i in range(x - 1):
# 有序标记，每一轮的初始是true，用于判断元素间是否需要交换
isSorted = True
# 这个循环负责控制比较的元素个数
for j in range(0, x - 1 - i):
# 交换顺序
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j +1], list[j]
# 有交换行为设为 False
isSorted = False
# 无交换行为（isSorted = True），直接跳过本次循环
if isSorted:
break
return list
list = [3,1,2,4,5]
print(bubble_sort(list)) 上述代码中加入了一个标志位 isSorted ，利用布尔变量 isSorted 作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-07-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录