冒泡与插入排序

202321336073 毛敏磊

于 2025-04-29 23:38:37 发布

阅读量273

点赞数 3

文章标签：排序算法算法

本文链接：https://blog.csdn.net/mml12/article/details/147621704

版权

冒泡排序与插入排序：基础排序算法解析

冒泡排序 (Bubble Sort)

动态演示

冒泡排序动态图
图1：冒泡排序的动画过程（来源：VisuAlgo算法可视化平台）1

核心步骤

1.比较相邻元素：从数组首端开始，依次比较相邻元素。
2.交换位置：若当前元素大于后一个元素，则交换位置。
3.重复遍历：每轮遍历将最大值“冒泡”到数组末尾，遍历次数逐轮减少。

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

时间复杂度

最坏情况：O(n²) - 当列表是逆序的时候

最好情况：O(n) - 当列表已经有序时（可以通过添加标志位优化）

平均情况：O(n²)

空间复杂度

O(1) - 只需要常数级别的额外空间

插入排序 (Insertion Sort)

动态演示
在这里插入图片描述

核心步骤

1.构建有序子序列：从第二个元素开始，逐步将元素插入已排序的子序列。
2.后移元素腾位：若当前元素小于子序列元素，则子序列元素后移。
3.插入目标位置：找到合适位置后插入当前元素。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr