刷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. 外循环（迭代排序的过程）：外循环控制内循环的重复执行，每执行完一次内循环后，排序的范围就减少一个元素（因为每次内循环都会将当前未排序部分的最大元素放到正确的位置）。外循环持续进行，直到整个数组排序完成。

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

方便大家理解 这里调用 imagemagick 记录每一次的排序图片生成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)