Python冒泡排序算法及其优化「建议收藏」

Python冒泡排序算法及其优化「建议收藏」冒泡排序所谓冒泡,就是将元素两两之间进行比较,谁大就往后移动,直到将最大的元素排到最后面,接着再循环一趟,从头开始进行两两比较,而上一趟已经排好的那个元素就不用进行比较了。(图中排好序的元素标记为黄色柱子)冒泡排序动图演示上python代码:defbubble_sort(items):foriinrange(len(items)-1):…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

冒泡排序

所谓冒泡,就是将元素两两之间进行比较,谁大就往后移动,直到将最大的元素排到最后面,接着再循环一趟,从头开始进行两两比较,而上一趟已经排好的那个元素就不用进行比较了。(图中排好序的元素标记为黄色柱子)

Python冒泡排序算法及其优化「建议收藏」
冒泡排序动图演示

python代码:

def bubble_sort(items):
    for i in range(len(items) - 1):
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return items


list1 = [2,1,9,11,10,8,7]
print(bubble_sort(list1))

输出结果:

[1, 2, 7, 8, 9, 10, 11]

这是冒泡排序最普通的写法,但你会发现它有一些不足之处,比如列表:[1,2,3,4,7,5,6],第一次循环将最大的数排到最后,此时列表已经都排好序了,就是不用再进行第二次、第三次…

冒泡排序优化一:

设定一个变量为False,如果元素之间交换了位置,将变量重新赋值为True,最后再判断,在一次循环结束后,变量如果还是为False,则brak退出循环,结束排序。

def bubble_sort(items):
    for i in range(len(items) - 1):
        flag = False
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                flag = True
        if not flag:
            break
    return items

冒泡排序优化二:搅拌排序 / 鸡尾酒排序

上面这种写法还有一个问题,就是每次都是从左边到右边进行比较,这样效率不高,你要考虑当最大值和最小值分别在两端的情况。写成双向排序提高效率,即当一次从左向右的排序比较结束后,立马从右向左来一次排序比较。

Python冒泡排序算法及其优化「建议收藏」
双向排序动图演示

python代码:

def bubble_sort(items):
    for i in range(len(items) - 1):
        flag = False
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                flag = True
        if flag:
            flag = False
            for j in range(len(items) - 2 - i, 0, -1):
                if items[j - 1] > items[j]:
                    items[j], items[j - 1] = items[j - 1], items[j]
                    flag = True
        if not flag:
            break
    return items

冒泡排序优化三:

最后要考虑的情况就是,如果给你的不是列表,而是对象,或者列表里面都是字符串,那么上述的代码也就没有用了,这时候你就要自定义函数了,并将其当成参数传入bubble_sort函数

python代码:

def bubble_sort(items, comp=lambda x, y: x > y):
    for i in range(len(items) - 1):
        flag = False
        for j in range(len(items) - 1 - i):
            if comp(items[j],items[j + 1]):
                items[j], items[j + 1] = items[j + 1], items[j]
                flag = True
        if flag:
            flag = False
            for j in range(len(items) - 2 - i, 0, -1):
                if comp(items[j - 1],items[j]):
                    items[j], items[j - 1] = items[j - 1], items[j]
                    flag = True
        if not flag:
            break
    return items

list2 = ['apple', 'watermelon', 'pitaya', 'waxberry', 'pear']
print(bubble_sort(list2,lambda s1,s2: len(s1) > len(s2)))  #按照字符串长度从小到大来排序

输出结果:

['pear', 'apple', 'pitaya', 'waxberry', 'watermelon']

类似的,当有人叫你给一个类对象排序时,也可以传入lambda 自定义函数。

class Student():
    """学生"""

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f'{self.name}: {self.age}'

items1 = [
        Student('Wang Dachui', 25),
        Student('Di ren jie', 38),
        Student('Zhang Sanfeng', 120),
        Student('Bai yuanfang', 18)
    ]

print(bubble_sort(items1, lambda s1, s2: s1.age > s2.age))

输出结果:按照年龄从小到大排序

[Bai yuanfang: 18, Wang Dachui: 25, Di ren jie: 38, Zhang Sanfeng: 120]

 

以上就是关于冒泡排序的原理,以及一些优化写法,希望看完对你会有所帮助~

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/181713.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java—java.util.calendar类详解「建议收藏」

    Java—java.util.calendar类详解「建议收藏」目录一、概述二、静态常量三、静态方法四、实例五、GregorianCalendar类一、概述java.util.Calendar类是一个抽象类,是java日期处理的核心类之一。Calendar类为操作日历字段,及其与特定瞬间之间的转换提供了方法。日历字段包含YEAR、MONTH、DAY_OF_MONTH、HOUR等,它们都是Calendar类的静态常量。二、静态常量…

  • 希尔排序算法实例讲解_十大算法排名

    希尔排序算法实例讲解_十大算法排名一、什么是希尔排序1.概念希尔排序(ShellSort)是把记录按下标的一定增量分组,对每组使用插入排序算法,随着增量逐渐减少,每组包含的元素越来越多,当增量减至1时,所有元素被分为一组,算法终止2.算法原理这是一个无序数列:1、5、8、4、7、2、6、3,我们要将它按从小到大排序。按照希尔排序的思想,我们先把数列进行分组排序首先,我们选择序列长度的一半4,作为增量进行分组如果所示,1和7一组,5和2一组,8和6一组,4和3一组,共四组然后,我们对每一组进行插入排序,排序后序列如下经

    2022年10月27日
  • 下载scrapy失败_手机安装包无法安装怎么办

    下载scrapy失败_手机安装包无法安装怎么办Scrapy安装有问题的,按照这个路径配置下anaconda的环境变量然后进入pycharm里的工作目录输入pipinstall-ihttps://pypi.tuna.tsinghua.edu.cn/simplescrapy安装完成后在cmd中输入scrapy,显示下图内容则证明安装成功:…

  • mac远程连接mysql「建议收藏」

    mac远程连接mysql「建议收藏」sudosshroot@IPmysql-uroot-p-hIP

    2022年10月13日
  • Windows系统日志分析_python日志采集分析

    Windows系统日志分析_python日志采集分析日志文件,它记录着Windows系统及其各种服务运行的每个细节,对增强Windows的稳定和安全性,起着非常重要的作用。但许多用户不注意对它保护,一些“不速之客”很轻易就将日志文件清空,给系统带来严重的安全隐患。  一、什么是日志文件  日志文件是Windows系统中一个比较特殊的文件,它记录着Windows系统中所发生的一切,如各种系统服务的启动、运行、关闭等信息。Windows日志包括应用

  • phpstorm 2021.7.20 激活码【中文破解版】

    (phpstorm 2021.7.20 激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlML…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号