Python 实现冒泡排序：从原理到代码
在学习编程的过程中，排序算法是绕不开的话题。冒泡排序作为最经典的排序算法之一，以其简单易懂的特点，成为了初学者入门排序算法的首选。今天，就让我们一起深入学习冒泡排序的原理，并用 Python 实现它。
一、冒泡排序的原理
冒泡排序是一种简单的排序算法，它重复地遍历待排序的数组，比较每对相邻元素，如果它们的顺序错误就把它们交换过来。遍历数组的工作是重复进行的，直到没有再需要交换的元素为止，也就是说该数组已经排序完成。
（一）排序过程
- 比较相邻元素：从数组的第一个元素开始，比较每对相邻的元素。
- 交换元素：如果前一个元素大于后一个元素，则交换它们的位置。
- 重复操作：重复上述步骤，直到整个数组排序完成。
（二）示例
假设我们有一个数组 [64, 34, 25, 12, 22, 11, 90]，冒泡排序的过程如下：
-
第一次遍历：
- 比较 64 和 34，交换位置 →
[34, 64, 25, 12, 22, 11, 90] - 比较 64 和 25，交换位置 →
[34, 25, 64, 12, 22, 11, 90] - 比较 64 和 12，交换位置 →
[34, 25, 12, 64, 22, 11, 90] - 比较 64 和 22，交换位置 →
[34, 25, 12, 22, 64, 11, 90] - 比较 64 和 11，交换位置 →
[34, 25, 12, 22, 11, 64, 90] - 比较 64 和 90，不交换位置 →
[34, 25, 12, 22, 11, 64, 90]
- 比较 64 和 34，交换位置 →
-
第二次遍历：
- 比较 34 和 25，交换位置 →
[25, 34, 12, 22, 11, 64, 90] - 比较 34 和 12，交换位置 →
[25, 12, 34, 22, 11, 64, 90] - 比较 34 和 22，交换位置 →
[25, 12, 22, 34, 11, 64, 90] - 比较 34 和 11，交换位置 →
[25, 12, 22, 11, 34, 64, 90] - 比较 34 和 64，不交换位置 →
[25, 12, 22, 11, 34, 64, 90]
- 比较 34 和 25，交换位置 →
-
重复上述过程，直到整个数组排序完成。
二、Python 实现冒泡排序
（一）基本实现
以下是用 Python 实现冒泡排序的代码：
def bubble_sort(arr):n = len(arr)for i in range(n):# 标志位，用于优化算法swapped = Falsefor 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:breakreturn arr# 测试代码
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("排序后的数组:", sorted_arr)
（二）优化实现
虽然冒泡排序的时间复杂度为 O(n²)，但可以通过一些优化来提高效率。例如，如果在某次遍历中没有发生交换，说明数组已经排序完成，可以提前结束排序。
def bubble_sort_optimized(arr):n = len(arr)for i in range(n):swapped = Falsefor j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr# 测试代码
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort_optimized(arr)
print("排序后的数组:", sorted_arr)
三、冒泡排序的性能分析
（一）时间复杂度
- 最坏情况：O(n²)，当数组完全逆序时，需要进行 n*(n-1)/2 次比较和交换。
- 最好情况：O(n)，当数组已经排序完成时，只需要进行一次遍历即可。
- 平均情况：O(n²)，在大多数情况下，冒泡排序的时间复杂度为 O(n²)。
（二）空间复杂度
冒泡排序是一种原地排序算法，空间复杂度为 O(1)。
（三）稳定性
冒泡排序是一种稳定的排序算法，即相等的元素在排序后仍然保持原来的顺序。
四、总结
通过本文的介绍，你已经掌握了冒泡排序的原理和 Python 实现方法。以下是关键点总结：
- 原理：通过比较相邻元素并交换位置，逐步将最大值“冒泡”到数组的末尾。
- 实现：使用两层循环实现冒泡排序，通过标志位优化算法。
- 性能分析：时间复杂度为 O(n²)，空间复杂度为 O(1)，是一种稳定的排序算法。
虽然冒泡排序在实际应用中不如快速排序、归并排序等高效，但它简单易懂，适合初学者学习排序算法的基本思想。