插入排序与冒泡排序详解：Python实现、时间复杂度分析与应用场景

排序算法是算法基础的核心组成部分，正式讲解前，我们先明确两个关键分类标准，以帮助您更好地理解算法的特性：

• 按是否占用额外空间划分：
  • 内部排序：所有数据在内存中完成排序（本文介绍的插入排序、冒泡排序均属于此类）。
  • 外部排序：数据量过大，需借助硬盘等外部存储设备辅助排序。
• 按稳定性划分：
  • 稳定排序：排序后，相同元素的相对位置保持不变。
  • 不稳定排序：相同元素的相对位置可能因排序而发生改变。

插入排序：像整理扑克牌一样排序

算法思路

插入排序的逻辑非常贴近生活中整理扑克牌的场景：

1. 拿到第一张牌时，默认它已经是有序的。
2. 摸到下一张新牌，将它从右向左与手中已排好序的牌逐一比较。
3. 找到合适的位置后，将新牌插入，确保手上的牌始终保持有序状态。
4. 重复上述步骤，直到所有的牌都被处理完毕。

代码实现 (Python)

def insertion_sort(arr):
    # 获取数组长度
    n = len(arr)
    # 从第二个元素开始插入（第一个元素默认有序）
    for p in range(1, n):
        # 暂存当前待插入的元素
        tmp = arr[p]
        # 从当前元素的前一个位置开始向前比较
        j = p
        while j > 0 and arr[j-1] > tmp:
            # 比tmp大的元素向后移动一位
            arr[j] = arr[j-1]
            j -= 1
        # 找到合适位置，插入tmp
        arr[j] = tmp
    return arr

# 测试示例
test_arr = [13, 5, 11, 14, 15]
sorted_arr = insertion_sort(test_arr)
print("插入排序结果：", sorted_arr)  # 输出：[5, 11, 13, 14, 15]

算法分析

• 时间复杂度：最坏情况（数组完全逆序）下，第2个元素需对比1次，第3个元素需对比2次……第n个元素需对比n-1次，总对比次数为 1+2+…+(n-1) = n(n-1)/2，因此时间复杂度为 O(n²)。
• 稳定性：稳定排序。因为插入时只移动比当前元素大的值，相等元素不会改变相对顺序。
• 核心优势：每一次插入操作都有可能消除当前元素之前的多个逆序对。因此，对于接近有序的数组，其效率会远高于理论最坏复杂度。

冒泡排序：像气泡上升一样排序

算法思路

冒泡排序的灵感来源于水中气泡上升的过程——轻的气泡会逐渐上浮。算法逻辑如下：

1. 对数组中相邻的两个元素进行逐一比较。
2. 如果前一个元素大于后一个元素，就交换它们的位置。
3. 每进行一轮完整的遍历，当前未排序部分中最大的元素就会像气泡一样“浮”到数组的末尾正确位置。
4. 重复上述过程，总共进行 n-1 轮即可完成排序（最后一轮只剩一个元素，自然有序）。

代码实现 (Python)

def bubble_sort(arr):
    n = len(arr)
    # 进行n-1轮排序（每轮确定一个最大值的位置）
    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

# 测试示例
test_arr = [13, 5, 11, 14, 15]
sorted_arr = bubble_sort(test_arr)
print("冒泡排序结果：", sorted_arr)  # 输出：[5, 11, 13, 14, 15]

算法分析

• 时间复杂度：最坏情况下，第一轮对比 n-1 次，第二轮对比 n-2 次……第 n-1 轮对比1次，总对比次数同样为 n(n-1)/2，时间复杂度为 O(n²)。
• 稳定性：稳定排序。因为只有相邻元素大小不同时才会交换，相等元素不会发生位置变动。
• 核心特点：每一轮排序只能让一个最大元素归位，每一次交换仅消除一个逆序对。其效率通常低于插入排序，但逻辑极为直观，易于理解和实现。

核心对比与总结

总的来说，插入排序和冒泡排序都是基础的内部稳定排序算法，时间复杂度均为 O(n²)，仅适合处理小规模数据。在实际应用中，插入排序因其更高的元素移动效率而更受青睐；而冒泡排序则以逻辑简单著称，是入门深入理解数据结构的经典案例。