当前位置: 首页 > article >正文

算法---冒泡法

冒泡排序的基本思路

对所有相邻记录的值进行比较,如果符合条件,则将两者进行交换,最终达到有序化。

冒泡排序的基本步骤

  1. 比较相邻的元素,如果前一个比后一个大(升序),调换位置
  2. 对每一对响铃的元素进行重复的工作,每步完成后,最大的元素出现在末尾
  3. 对上步骤重复,直到数组有序

代码

class Solution:

    def bubbling(self, arr):
        n = len(arr)
        for i in range(n):
            for j in range(n - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
        return arr


if __name__ == "__main__":
    arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
    s = Solution()
    res = s.bubbling(arr)
    print(res)

 冒泡排序的优化

在纸上自己一步一步演练的人就会发现一个问题,比如说上面的例子中,8到末尾之后,再次遍历的时候,前边元素并没有比8大的,但是还会判断8,这一步如何优化呢?

代码

class Solution:

    def bubbling(self, arr):
        n = len(arr)
        for i in range(n):
            for j in range(n - 1 - i):  # 优化点在这一行
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
        return arr


if __name__ == "__main__":
    arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
    s = Solution()
    res = s.bubbling(arr)
    print(res)

那这就完了吗?还有没有优化的地方呢?其实我们在第二层for循环中加个打印可以看出,在经过几轮排序之后,其实已经有序了,但是依然完成了整个遍历

我们先来看下代码

再次优化代码

class Solution:

    def bubbling(self, arr):
        n = len(arr)
        num = 0
        for i in range(n):
            flag = False
            print("第%s次执行" % num)

            for j in range(n - 1 - i):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    flag = True

            if not flag:
                break
            num += 1
        return arr


if __name__ == "__main__":
    arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
    s = Solution()
    res = s.bubbling(arr)
    print(res)
  • 优化后的代码将 flag变量初始化为 False,在内层循环中,如果发生元素交换,则将 flag置为 True,表示发生了交换操作。
  • 在内层循环结束后,检查 flag的值,如果 flag为 False,说明在这一轮比较中没有元素交换,列表已经有序,此时使用 break 语句提前结束排序过程,避免不必要的比较操作。

这样的优化可以提高冒泡排序的性能,特别是对于部分有序的列表,避免进行多余的比较和交换操作,提升了代码的执行效率。

在代码中加了打印,我们做下对比,上面是加了标志位的,执行了5次就结束了,我们去掉标志位的代码看下,大家看到了吧,执行了10次


http://www.kler.cn/a/513401.html

相关文章:

  • HTML语言的数据库编程
  • WPS数据分析000001
  • 如何在龙蜥 OS(AliOS)上安装极狐GitLab?
  • 浅谈计算机网络03 | 现代网络组成
  • 有限元分析学习——Anasys Workbanch第一阶段笔记(13)网格单元分类、物理场与自由度概念
  • 深度学习中的张量 - 使用PyTorch进行广播和元素级操作
  • 推荐一个小而美的 Toast 插件 (一键复制使用)
  • Dart语言的学习路线
  • YOLOv10-1.1部分代码阅读笔记-dist.py
  • 61,【1】BUUCTF WEB BUU XSS COURSE 11
  • 大牙的2024年创作总结
  • 求解ssp 问题建模
  • 个人职业发展与AI赋能的前端开发
  • 交换机Console密码忘记无法登录设备怎么办?
  • ubuntu16.04 VSCode下cmake+clang+lldb调试c++
  • 线程池实现
  • 36. K11364 剑法
  • Erlang语言的面向对象编程
  • 以 RFID 为钥,开启民兵装备管理的科技之门
  • linux 下tensorrt的yolov8的前向推理(python 版本)的实现
  • 【Linux】多线程(一)
  • JavaScript笔记进阶篇01——作用域、箭头函数、解构赋值
  • Java 中的同步与并发工具类
  • JAVA-Exploit编写(8-10)--http-request库编写exp批量利用
  • 后端:MyBatis
  • Hive: Hive的优缺点,使用方式,判断Hive是否启动(jps),元数据的存储,Hive和Hadoop的关系