Python 如何优化冒泡排序

清疚 2022-05-19 05:26 177阅读 0赞

> 微信公众号：一个优秀的废人  
> 如有问题或建议，请后台留言，我会尽力解决你的问题。

![冒泡排序.jpg][.jpg]

#### 什么叫冒泡排序法？ ####

相信有接触过算法的朋友多少都了解冒泡排序法，那么什么是冒泡排序法呢？冒泡排序，英文名称（Bubble Sort）是一种基础的交换排序算法，在日常工作中经常会用到，例如：页面数据需按时间先后排序，这本质上也是一种冒泡排序法。

喝过可乐的朋友都知道，可乐里面的气泡会向上浮，这就是冒泡排序一种最形象的例子。至于有些朋友问，是大的气泡先上浮还是小的先上浮呢？这就取决于你的需求去做控制了。

先上动图，再结合代码介绍一下冒泡排序算法的执行过程。

![冒泡排序.gif][.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 作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。

最后，如果对 Python 、Java 感兴趣请长按二维码关注我的公众号，我会努力带给你们价值，赞赏就不必了，能力没到，受之有愧，如果觉得有帮助点个赞就好，没帮助的话忽略就好。

![一个优秀的废人][1240]

[.jpg]: /images/20220519/f0200ce28a6444569950447a0b421b28.png
[.gif]: /images/20220519/a346fe864d0b42d2a9655063ac41e2e7.png
[1240]: /images/20220519/a9ccfbb179f5478d9086dd2bf1dbd68b.png