专栏首页用户5521492的专栏Python 如何优化冒泡排序

Python 如何优化冒泡排序

什么叫冒泡排序法?

相信有接触过算法的朋友多少都了解冒泡排序法,那么什么是冒泡排序法呢?冒泡排序,英文名称(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 作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。

本文分享自微信公众号 - 一个优秀的废人(feiren_java),作者:nasus

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 除了不要 SELECT * ,数据库还有哪些技巧?

    能用TINYINT就不用SMALLINT,能用SMALLINT就不用INT,道理你懂的,磁盘和内存消耗越小越好嘛。

    一个优秀的废人
  • SpringBoot 实战 (七) | 默认日志配置

    默认情况下,Spring Boot 用 Logback 来记录日志,并用 INFO 级别输出到控制台。如果你在平常项目中用过 Spring Boot,你应该已经...

    一个优秀的废人
  • 一个 TCP 连接可以发多少个 HTTP 请求?

    相信大多数准备过的同学都能回答出来,但是如果继续问:收到的 HTML 如果包含几十个图片标签,这些图片是以什么方式、什么顺序、建立了多少连接、使用什么协议被下载...

    一个优秀的废人
  • JAVA中的List的使用

    战神伽罗
  • 算法02 七大排序之:直接选择排序和堆排序

    上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

    nnngu
  • Python:列表操作命令

    示例:三个函数:min(),max()sum()分别取列表中最小值,最大值,数值总和

    py3study
  • python中list的各种方法使用

    参考链接: Python中list的方法 2| del, remove(), sort(), insert(), pop(), extend()…

    用户7886150
  • Java中List集合去除重复数据的方法

    4.把list里的对象遍历一遍,用list.contain(),如果不存在就放入到另外一个list集合中

    三哥
  • python 集合

    说明: 拿list_1每一个元素去list_2中查找,如果有,直接忽略,否则就直接输出。

    py3study
  • Python数据分析之锁具装箱问题问题重述问题分析建模与求解

    罗罗攀

扫码关注云+社区

领取腾讯云代金券