LeetCode 冒泡排序题解题目描述实现冒泡排序算法对一个整数数组进行排序。示例输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]解题思路方法冒泡排序思路冒泡排序的核心思想是通过相邻元素的比较和交换使得每一轮循环都能将当前未排序部分的最大值移到末尾。具体步骤遍历数组比较相邻的两个元素。如果前一个元素大于后一个元素则交换它们。重复上述步骤直到没有需要交换的元素。复杂度分析时间复杂度O(n²)其中 n 是数组的长度。最坏情况下需要进行 n(n-1)/2 次比较和交换。空间复杂度O(1)只需要常数级的额外空间。代码实现方法冒泡排序# 冒泡排序 def bubble_sort(arr): n len(arr) # 遍历所有数组元素 for i in range(n): # 标记本轮是否有交换 swapped False # 最后 i 个元素已经排好序不需要再比较 for j in range(0, n - i - 1): # 如果当前元素大于下一个元素交换它们 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果本轮没有交换说明数组已经有序提前结束 if not swapped: break return arr # 测试 def test_bubble_sort(): arr [64, 34, 25, 12, 22, 11, 90] print(bubble_sort(arr)) # 输出[11, 12, 22, 25, 34, 64, 90] arr [5, 4, 3, 2, 1] print(bubble_sort(arr)) # 输出[1, 2, 3, 4, 5] arr [1, 2, 3, 4, 5] print(bubble_sort(arr)) # 输出[1, 2, 3, 4, 5] if __name__ __main__: test_bubble_sort()测试用例测试用例 1基本情况输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]测试用例 2逆序数组输入[5, 4, 3, 2, 1]输出[1, 2, 3, 4, 5]测试用例 3已排序数组输入[1, 2, 3, 4, 5]输出[1, 2, 3, 4, 5]总结冒泡排序是一种简单的排序算法它通过相邻元素的比较和交换来实现排序。虽然冒泡排序的时间复杂度较高但它的实现简单对于小规模数据或基本有序的数据来说效率还是可以接受的。冒泡排序的核心思想是通过相邻元素的比较和交换使得每一轮循环都能将当前未排序部分的最大值移到末尾。掌握冒泡排序的原理和实现对于理解排序算法的基本思想非常重要。