LeetCode 第二题:冒泡排序详解 【2/1000】含imagemagick动态效果图

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python
作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,欢迎关注公众号 数据分析螺丝钉  回复关键词 【学习资料】领取notebook和代码调试过程,一起打怪升级

今日推荐:imagemagick 是一个功能强大的图像处理工具,本文用来记录每个运行的步骤通过GIF来呈现

 

题目描述

​输入:[74,55,35,79,57,71,81,5,82,1]

输出:[1,5,35,55,57,71,74,79,81,82]

冒泡算法

冒泡排序是计算机科学中最简单的排序算法之一。这个算法的名字来源于较小的元素会通过交换逐渐“冒泡”到列表的顶端,就像水中的气泡一样。

算法原理

冒泡排序算法的核心原理基于两个嵌套循环,通过反复交换数组中相邻的元素,直到整个数组排序完成。其主要过程分为两部分:

  1. 内循环(比较与交换):算法从数组的第一个元素开始,比较相邻的元素对 (j, j+1)。如果 j 位置的元素大于 j+1 位置的元素(对于升序排序),则这两个元素的位置会被交换。这一过程一直重复,直到到达数组的末尾。每完成一轮内循环,都能保证这一轮中最大的元素被"冒泡"到其最终位置(即数组的最右端)。

    1. 要注意的优化:防止已经排序的重复执行,通过增加一个标志位 flag ,若在某轮「内循环」中未执行任何交换操作,则说明数组已经完成排序,直接返回结果即可。这个在已经排序好的情况下 可以减少不必要的比较

  2. 外循环(迭代排序的过程):外循环控制内循环的重复执行,每执行完一次内循环后,排序的范围就减少一个元素(因为每次内循环都会将当前未排序部分的最大元素放到正确的位置)。外循环持续进行,直到整个数组排序完成。

让我们一起如图跟着一起过一遍

 

7fce2b2ccb50e7b241c9ff5b3afd52fd.png

方便大家理解 这里调用 imagemagick 记录每一次的排序图片生成GIF动态演示每个冒泡的步骤

 

b2372abc5d03cef4cf7cc7d98f258489.gif

冒泡算法

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # 初始化标志位
        for j in range(1, n - i):
            steps += 1  # Increment steps for each comparison
            if arr[j - 1] > arr[j]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

算法复杂度

时间复杂度:平均和最坏情况下是O(n^2),最佳情况是O(n)(如果列表已经排序)

空间复杂度:O(1),因为它是一个原地排序算法

完整代码

有使用动态效果图展示,所以需要先安装 imagemagick,安装步骤简介

Windows:

  1. 访问 ImageMagick 的官方下载页面: ImageMagick Download
  2. 下载适用于 Windows 的安装程序。
  3. 运行安装程序并遵循提示进行安装。在安装过程中,确保选中“Add application directory to your system path”以便在任何命令行窗口中使用 ImageMagick。

macOS:

可以使用 Homebrew 安装 ImageMagick:

  1. 打开终端。
  2. 如果您还没有安装 Homebrew,请先安装它。可以从 Homebrew 官网 获取安装命令。
  3. 安装 ImageMagick,运行以下命令:
brew install imagemagick
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
​
def bubble_sort(arr):
    """
    Performs bubble sort on a list and counts the steps.
​
    Parameters:
    arr (list): The list to be sorted.
​
    Returns:
    (list, int): A tuple of the sorted list and the number of steps taken.
    """
    n = len(arr)
    steps = 0  # Initialize step count
    for i in range(n):
        swapped = False
        for j in range(1, n - i):
            steps += 1  # Increment steps for each comparison
            if arr[j - 1] > arr[j]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break
    return arr, steps
​
def bubble_sort_unoptimized(arr):
    n = len(arr)
    steps = 0  # Initialize step count
    for i in range(n): # 外循环
        for j in range(0, n-i-1): # 内循环
            steps += 1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr,steps
​
def initialize_animation(arr):
    """
    Initializes the bar chart and text annotations for the animation.
​
    Parameters:
    arr (list): The list based on which bars are plotted.
​
    Returns:
    tuple: Contains the figure, axis, bars, and text annotations.
    """
    fig, ax = plt.subplots()
    bar_rects = ax.bar(range(len(arr)), arr, color='skyblue')
    ax.set_ylim(0, int(max(arr) * 1.1))
    text_annotations = [ax.text(rect.get_x() + rect.get_width() / 2, rect.get_height(), str(val), ha='center', va='bottom') 
                        for rect, val in zip(bar_rects, arr)]
    steps_text = ax.text(0.02, 0.95, '', transform=ax.transAxes)
    return fig, ax, bar_rects, text_annotations, steps_text
​
def update_animation(frame, arr, bar_rects, text_annotations, steps_text, steps_count):
    """
    Update function for the animation that shows the sorting process.
​
    Parameters:
    frame (int): The current frame number in the animation.
    arr (list): The list being sorted.
    bar_rects (BarContainer): The bars representing the list elements.
    text_annotations (list of Text): The text annotations for each bar.
    steps_text (Text): The text annotation for the number of steps.
    steps_count (list of int): A list containing a single integer that counts the steps.
    """
    n = len(arr)
    swapped = False
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]  # Swap elements
            swapped = True
            steps_count[0] += 1  # Increment the steps count
            break
    # Update the bars and text annotations
    for rect, val, text in zip(bar_rects, arr, text_annotations):
        rect.set_height(val)
        text.set_text(str(val))
        text.set_position((rect.get_x() + rect.get_width() / 2, val))
    steps_text.set_text(f'Steps: {steps_count[0]}')  # Update the steps display
    if not swapped:
        anim.event_source.stop()  # Stop the animation if no swaps occurred
​
# Main execution part
if __name__ == "__main__":
    # Define the unsorted array
    unsorted_arr = [74, 55, 35, 79, 57, 71, 81, 5, 82, 1]
    # Perform bubble sort and get the sorted array with step count
    sorted_arr, steps = bubble_sort(unsorted_arr.copy())
    print(f'Sorted array: {sorted_arr}')
    print(f'Steps taken: {steps}')
​
    # Initialize the animation plot
    fig, ax, bar_rects, text_annotations, steps_text = initialize_animation(unsorted_arr)
​
    # Create the animation object
    anim = FuncAnimation(fig, update_animation, fargs=(unsorted_arr, bar_rects, text_annotations, steps_text, [0]),
                         frames=range(len(unsorted_arr)**2), interval=500, repeat=False)
​
    # Save the animation to a GIF file
    anim.save('bubble_sort_with_steps.gif', writer='pillow', fps=2)

 

 

 

 

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/518691.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用微带线快速进行电感、电容的等效(Matlab代码实现)

使用微带线快速进行电感、电容的等效(Matlab代码实现) 目录 使用微带线快速进行电感、电容的等效(Matlab代码实现)1、高低阻抗微带线的近似等效2、等效电容的ADS测试3、等效电感的ADS测试 1、高低阻抗微带线的近似等效 更加精确的…

利用JS、CSS实现列表自动滑动滚动

零.业务需求 这几天在做大屏项目&#xff0c;对于大屏有很多信息需要实时滚动&#xff0c;废了点力气学的明明白白的&#xff0c;特来记录供大家学习。 0.1实现效果 一.逻辑分析 1.1滑动窗口和滚动条 当我们使用<table>或者<ul>标签时&#xff0c;我们可以制作…

蓝桥杯第十四届C++A组(未完)

【规律题】平方差 题目描述 给定 L, R&#xff0c;问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 。 输入格式 输入一行包含两个整数 L, R&#xff0c;用一个空格分隔。 输出格式 输出一行包含一个整数满足题目给定条件的 x 的数量。 样例输入 1 5 样例输出 …

Redis中的Sentinel(二)

Sentinel 初始化Sentinel状态。 在应用了Sentinel的专用代码之后&#xff0c;接下来&#xff0c;服务器会初始化一个sentinel.c/sentinelState结构(简称Sentinel状态),这个结构 保存了服务器中所有和Sentinel功能有关的状态(服务器的一般状态仍然由redis.h/redisServer保存);…

【java数据结构-二叉树(上)】

java数据结构-二叉树&#xff08;上&#xff09; 二叉树的概念二叉树的节点介绍 二叉树构造如何使用兄弟表示法构造二叉树两种特别的二叉树二叉树的基本性质&#xff1a; 二叉树的存储二叉树的遍历&#xff1a;前序遍历&#xff1a;中序遍历&#xff1a;后序遍历&#xff1a;层…

最新ChatGPT4.0工具使用教程:GPTs,Midjourney绘画,AI换脸,GPT语音对话,文档分析一站式系统

一、前言 ChatGPT3.5、GPT4.0、相信对大家应该不感到陌生吧&#xff1f;简单来说&#xff0c;GPT-4技术比之前的GPT-3.5相对来说更加智能&#xff0c;会根据用户的要求生成多种内容甚至也可以和用户进行创作交流。 然而&#xff0c;GPT-4对普通用户来说都是需要额外付费才可以…

基于RDMA的云服务能力实践与探索

01 背景 随着基于大数据大模型构建的数据系统越来越有商业价值&#xff0c;机器学习的玩家也越来越多&#xff0c;数据量越来越大。为解决海量数据在服务器之间的同步效率问题&#xff0c;RDMA(Remote Direct Memory Access) 技术逐渐走进了网络技术人员的视野。RDMA为什么…

yolov8多分支任务头训练

目前已知的yolov8可以针对多个任务进行单独训练,但是暂时还没有开放针对多个任务头同时进行训练的教程,本文章针对yolov8的多任务训练进行详细介绍。 先放上效果图: 三个任务,分别是目标检测、可行驶区域、车道线,具体步骤请往下看。 一、环境配置 从如下github下载代码…

Flutter Don‘t use ‘BuildContext‘s across async gaps.

Flutter提示Don‘t use ‘BuildContext‘s across async gaps.的解决办法—flutter里state的mounted属性

10-热点文章-定时计算

xxl-Job分布式任务调度 1 今日内容 1.1 需求分析 目前实现的思路&#xff1a;从数据库直接按照发布时间倒序查询 问题1&#xff1a; 如何访问量较大&#xff0c;直接查询数据库&#xff0c;压力较大 问题2&#xff1a; 新发布的文章会展示在前面&#xff0c;并不是热点文章 …

交叉验证(Cross-Validation)

交叉验证的基本概念 交叉验证通常用于评估机器学习模型在未知数据上的性能。它将数据集分成k个不同的子集&#xff0c;然后进行k次训练和验证。在每次迭代中&#xff0c;选择一个子集作为测试集&#xff0c;其余的子集作为训练集。这样&#xff0c;每个子集都用作过测试集&…

Debian安装1panel管理面板教程-最新

1Panel 是一个现代化、开源的 Linux 服务器运维管理面板。 1Panel面板是一个强大的服务器管理工具&#xff0c;它通过提供一站式管理、易于使用的界面、高度的可定制性、安全可靠的性能、强大的扩展性以及活跃的社区支持&#xff0c;为用户提供了一个高效、便捷的管理解决方案…

华为云1核2G免费使用一年

个人用户专享云服务器、云数据库产品每天上午9:30开抢&#xff0c;其他产品每天0点开放领取&#xff0c;企业用户所有产品每天0点开放领取&#xff1b; 云产品体验名额有限&#xff0c;领完即止。详情&#xff1a;https://www.vpspick.com/vps/591.html 通用入门型 T6 云服务…

实验06_IPv6实验

目录 实验拓扑 实验需求 实验配置及其现象验证&#xff1a; (1)R1---R4的IPv6的地址配置&#xff0c;根据设备编码配置IPv6 (2)R6 通过无状态自动获取 IPv6 地址 (3)OSPFv3 配置&#xff0c;通过 OSPFv3 实现全网通&#xff08;区域划分根据拓扑图&#xff09; 实验拓扑 …

Linux存储的基本管理

实验环境&#xff1a; 系统里添加两块硬盘 ##1.设备识别## 设备接入系统后都是以文件的形式存在 设备文件名称&#xff1a; SATA/SAS/USB /dev/sda,/dev/sdb ##s SATA, dDISK a第几块 IDE /dev/hd0,/dev/hd1 ##h hard VIRTIO-BLOCK /de…

蓝桥杯(5):python动态规划DF[2:背包问题]

1 0-1背包介绍【每件物品只能拿1件或者不拿】 1.1 简介 贪心是不可以的&#xff01;&#xff01;&#xff01; 1.2 状态 及状态转移 转移解释&#xff1a;要么不选 则上一个直接转移过来【dp[i-1][j]】&#xff0c;要么是选这个之后体积为j 则上一个对应的就是【dp[i-1][j-wi]…

Vue 样式技巧总结与整理[中级局]

SFC&#xff08;单文件组件&#xff09;由 3 个不同的实体组成&#xff1a;模板、脚本和样式。三者都很重要&#xff0c;但后者往往被忽视&#xff0c;即使它可能变得复杂&#xff0c;且经常导致挫折和 bug。 更好的理解可以改善代码审查并减少调试时间。 这里有 7 个奇技淫巧…

CSS设置网页颜色

目录 前言&#xff1a; 1.颜色名字&#xff1a; 2.十六进制码&#xff1a; 3.RGB&#xff1a; 4.RGBA&#xff1a; 5.HSL&#xff1a; 1.hue&#xff1a; 2.saturation&#xff1a; 3.lightness&#xff1a; 6.HSLA&#xff1a; 前言&#xff1a; 我们在电脑显示器&…

高血压的常见症状,你是否了解并警惕?

高血压是一种慢性心血管疾病&#xff0c;它的形成和发展与很多种因素密切相关。导致高血压的重要因素之一就是不良的生活饮食习惯。 高血压严重危害着人的心脏、肾脏、大脑等这些人体重要的器官&#xff0c;会容易带来心脏病、肾功能衰竭等一系列疾病。今天我在来为大家讲解一…

CorelDRAW2024序列号破解版下载以及CorelDRAW新功能介绍

CorelDRAW Graphics Suite 2024破解版介绍 CorelDRAW Graphics Suite 2024 破解版是领先的专业图形设计软件套件&#xff0c;旨在提供多个精心设计的工具和丰富的功能&#xff0c;轻松提高您的技能睡哦平&#xff0c;您可以更好的完成矢量插图、完美的布局、高级的照片编辑和高…