LeetCode 冒泡排序题解

LeetCode 冒泡排序题解

题目描述

实现冒泡排序算法，对一个整数数组进行排序。

示例：

输入：[64, 34, 25, 12, 22, 11, 90]
输出：[11, 12, 22, 25, 34, 64, 90]

解题思路

方法：冒泡排序

思路：

• 冒泡排序的核心思想是通过相邻元素的比较和交换，使得每一轮循环都能将当前未排序部分的最大值移到末尾。
• 具体步骤：
  1. 遍历数组，比较相邻的两个元素。
  2. 如果前一个元素大于后一个元素，则交换它们。
  3. 重复上述步骤，直到没有需要交换的元素。

复杂度分析：

• 时间复杂度：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]

总结

冒泡排序是一种简单的排序算法，它通过相邻元素的比较和交换来实现排序。虽然冒泡排序的时间复杂度较高，但它的实现简单，对于小规模数据或基本有序的数据来说，效率还是可以接受的。

冒泡排序的核心思想是：通过相邻元素的比较和交换，使得每一轮循环都能将当前未排序部分的最大值移到末尾。

掌握冒泡排序的原理和实现，对于理解排序算法的基本思想非常重要。