手写冒泡排序及其优化策略

题目描述
冒泡排序是一种基础的交换排序算法，其核心思想是通过相邻元素的比较和交换，使较大（或较小）的元素逐步“浮”到数组的一端。要求手写冒泡排序，并分析其时间复杂度，同时针对原始算法的不足提出优化策略。

解题过程

1. 基础冒泡排序实现

• 核心逻辑：
  每一轮遍历数组，比较相邻元素 arr[j] 和 arr[j+1]，若逆序则交换。每轮结束后，当前未排序部分的最大元素会“冒泡”到正确位置。
• 代码示例（升序排序）：

  def bubble_sort_basic(arr):
      n = len(arr)
      for i in range(n):          # 遍历 n 轮
          for j in range(0, n-1): # 每轮比较未排序部分
              if arr[j] > arr[j+1]:
                  arr[j], arr[j+1] = arr[j+1], arr[j]  # 交换
      return arr
  

• 时间复杂度：
  • 最好情况（已排序）：O(n²)（仍需完整比较）。
  • 最坏/平均情况：O(n²)。
• 问题：即使数组提前有序，算法仍会执行全部轮次。

2. 优化1：提前终止

• 优化思路：若某一轮未发生任何交换，说明数组已有序，可提前结束排序。
• 实现方法：引入标志位 swapped 跟踪每轮是否发生交换。
• 代码示例：

  def bubble_sort_optimized(arr):
      n = len(arr)
      for i in range(n):
          swapped = False         # 标记本轮是否发生交换
          for j in range(0, n-1-i):  # 每轮后减少比较范围（末尾已有序）
              if arr[j] > arr[j+1]:
                  arr[j], arr[j+1] = arr[j+1], arr[j]
                  swapped = True
          if not swapped:         # 本轮无交换，提前退出
              break
      return arr
  

• 时间复杂度：
  • 最好情况（已排序）：O(n)（仅需一轮遍历）。
  • 最坏/平均情况：O(n²)。

3. 优化2：减少比较范围

• 优化思路：每轮排序后，数组末尾的 i 个元素已有序，无需再比较。
• 实现方法：内层循环的终止条件改为 n-1-i（已在上述代码中体现）。
• 效果：减少不必要的比较次数，但时间复杂度常数因子优化。

4. 优化3：记录最后交换位置

• 优化思路：若某一轮中最后一次交换发生在位置 last_swap，则 last_swap 之后的元素已有序，下一轮只需比较到 last_swap。
• 代码示例：

  def bubble_sort_super_optimized(arr):
      n = len(arr)
      last_swap = n - 1           # 初始化最后交换位置
      for i in range(n):
          swapped = False
          current_swap = 0        # 记录本轮最后交换位置
          for j in range(0, last_swap):  # 仅比较到上一轮最后交换位置
              if arr[j] > arr[j+1]:
                  arr[j], arr[j+1] = arr[j+1], arr[j]
                  swapped = True
                  current_swap = j  # 更新本轮最后交换位置
          last_swap = current_swap
          if not swapped:
              break
      return arr
  

• 适用场景：对部分有序数组（如 [3, 2, 1, 4, 5, 6]）效率显著提升。

总结

• 基础版本：理解冒泡排序的核心交换逻辑。
• 优化方向：通过提前终止和动态调整比较范围，减少无效操作。
• 面试要点：能够手写优化后的代码，并清晰解释每步优化的目的和效果。