冒泡排序算法
冒泡排序算法
一、冒泡排序核心思想
冒泡排序是一种简单的交换排序算法，核心逻辑为：重复遍历待排序数组，依次比较相邻元素，若顺序错误则交换位置。每轮遍历会将未排序部分的最大元素“浮”到末端，如同水中气泡上升，因此得名。
二、简洁实现代码
def bubble_sort(arr):
n = len(arr)
# 外层循环控制排序轮次（最多n-1轮，因最后一个元素无需比较）
for i in range(n - 1):
# 内层循环比较相邻元素，每轮后减少已排序的尾部元素比较
for j in range(n - 1 - i):
# 若前元素大于后元素，交换位置（升序排序，降序改为<）
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 示例调用
if __name__ == "__main__":
test_arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前数组：", test_arr) # 注：原数组已被修改，若需保留原数组可传入副本
sorted_arr = bubble_sort(test_arr)
print("排序后数组：", sorted_arr)三、代码说明
函数定义：
bubble_sort函数接收一个列表arr作为参数，返回排序后的列表。长度获取：
n = len(arr)获取数组长度，用于控制循环边界。外层循环：
range(n - 1)控制排序轮次，最多需要n-1轮即可完成排序（最后一个元素自然有序）。内层循环：
range(n - 1 - i)中，i为已完成排序的轮次，每轮后尾部会新增一个有序元素，因此减少i次比较，优化效率。交换逻辑：使用Python简洁的元组赋值语法
arr[j], arr[j + 1] = arr[j + 1], arr[j]完成元素交换，无需临时变量。示例调用：定义测试数组，调用排序函数后打印排序前后结果，直观展示效果。
四、运行结果
排序前数组： [64, 34, 25, 12, 22, 11, 90]
排序后数组： [11, 12, 22, 25, 34, 64, 90]五、时间复杂度分析
时间复杂度是衡量算法效率的核心指标，用于描述算法执行时间随输入规模增长的变化趋势。冒泡排序的时间复杂度需结合排序过程中元素的比较和交换次数分析，具体分为以下三种情况：
- 最坏情况时间复杂度：O(n²)
当待排序数组为逆序（如[90, 64, 34, 25, 22, 12, 11]）时，每轮遍历都需要对未排序部分的所有相邻元素进行比较，且每次比较后都需交换位置。
- 第1轮：比较n-1次，交换n-1次；
- 第2轮：比较n-2次，交换n-2次；
- ...
- 第n-1轮：比较1次，交换1次；
总比较次数为(n-1)+(n-2)+...+1 = n(n-1)/2，交换次数与比较次数相等，均为O(n²)，因此最坏情况时间复杂度为O(n²)。
最好情况时间复杂度：O(n)
当待排序数组已完全有序（如[11, 12, 22, 25, 34, 64, 90]）时，若使用优化后的冒泡排序算法（添加swapped标记），则第1轮遍历后未发生任何交换，直接退出循环。此时仅需遍历数组1次，比较n-1次，交换0次，时间复杂度降至O(n)；若使用基础版冒泡排序，仍需遍历n-1轮，时间复杂度仍为O(n²)，这也体现了优化的必要性。平均情况时间复杂度：O(n²)
平均情况需考虑所有可能的输入数组排列情况，通过概率统计可得，冒泡排序的平均比较次数和交换次数均为O(n²)，因此平均时间复杂度为O(n²)。
综上，冒泡排序属于时间复杂度为O(n²)的基础排序算法，其优势在于逻辑简单、实现容易，适合小规模数据排序；但对于大规模数据，效率较低，通常会选择快速排序、归并排序等O(nlogn)级别的算法。
六、优化说明（可选）
若数组在某轮遍历中未发生任何交换，说明数组已有序，可提前退出循环，进一步优化效率，优化后代码如下：
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n - 1):
swapped = False # 标记本轮是否发生交换
for j in range(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