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

本文主要是介绍刷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 comparisonif arr[j - 1] > arr[j]:arr[j], arr[j - 1] = arr[j - 1], arr[j]  # Swap the elementsswapped = Trueif 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 countfor i in range(n):swapped = Falsefor j in range(1, n - i):steps += 1  # Increment steps for each comparisonif arr[j - 1] > arr[j]:arr[j], arr[j - 1] = arr[j - 1], arr[j]  # Swap the elementsswapped = Trueif not swapped:breakreturn arr, steps
​
def bubble_sort_unoptimized(arr):n = len(arr)steps = 0  # Initialize step countfor i in range(n): # 外循环for j in range(0, n-i-1): # 内循环steps += 1if 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 = Falsefor i in range(n - 1):if arr[i] > arr[i + 1]:arr[i], arr[i + 1] = arr[i + 1], arr[i]  # Swap elementsswapped = Truesteps_count[0] += 1  # Increment the steps countbreak# Update the bars and text annotationsfor 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 displayif not swapped:anim.event_source.stop()  # Stop the animation if no swaps occurred
​
# Main execution part
if __name__ == "__main__":# Define the unsorted arrayunsorted_arr = [74, 55, 35, 79, 57, 71, 81, 5, 82, 1]# Perform bubble sort and get the sorted array with step countsorted_arr, steps = bubble_sort(unsorted_arr.copy())print(f'Sorted array: {sorted_arr}')print(f'Steps taken: {steps}')
​# Initialize the animation plotfig, ax, bar_rects, text_annotations, steps_text = initialize_animation(unsorted_arr)
​# Create the animation objectanim = 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 fileanim.save('bubble_sort_with_steps.gif', writer='pillow', fps=2)

 

 

 

 

 

 

这篇关于刷LeetCode:冒泡排序详解 【2/1000 第二题】含imagemagick动态效果图的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/867775

相关文章

闲置电脑也能活出第二春?鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言,在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况,这使得“存储焦虑”不再是个别现象,而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得,我们似乎正处在互联网信息飞速增长的阶段,对于存储的需求也将会不断扩大。对于苹果用户而言,这一问题愈发严峻,毕竟512GB和1TB版本的iPhone可不是人人都消费得起的,因此成熟的外置存储方案开

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

K8S(Kubernetes)开源的容器编排平台安装步骤详解

K8S(Kubernetes)是一个开源的容器编排平台,用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述: 安装步骤: 安装Docker:K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master:在集群中选择一台主机作为Master节点,安装K8S的控制平面组件,如AP

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L