小白向-python实现冒泡排序算法(带丰富案例)

一、冒泡排序的定义

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地遍历待排序的序列，每次比较相邻的两个元素，如果它们的顺序错误就交换位置。这个过程类似气泡从水底上升，因此得名“冒泡排序”。

---

二、冒泡排序的发展历史

冒泡排序最早由计算机科学家 John von Neumann 提出，并在 20 世纪 50 年代得到广泛使用。由于其实现简单，早期计算机教学中经常使用该算法作为入门排序算法之一。然而，由于它的时间复杂度较高，效率较低，现代大规模数据处理场景中很少使用。

---

三、冒泡排序的排序过程

基本步骤如下：

1. 从列表的第一个元素开始，依次比较相邻的两个元素，如果前一个比后一个大，则交换它们的位置；
2. 继续向后比较，重复上述操作，直至遍历至最后一个元素；
3. 经过一轮遍历后，最大（或最小）的元素会移动到正确位置；
4. 对未排序的部分重复上述过程，直到整个列表有序。

---

四、冒泡排序的基本原理

冒泡排序的核心思想是：通过相邻元素的比较与交换，使未排序的最大值逐步向数组末端移动。
其时间复杂度分析如下：

• 最坏情况（数组逆序）：时间复杂度为 O(n2)O(n^2)O(n2)；
• 最优情况（数组已排序）：时间复杂度为 O(n)O(n)O(n)，此时可以通过“冒泡排序优化”减少不必要的比较；
• 平均情况：时间复杂度仍为 O(n2)O(n^2)O(n2)。

---

五、冒泡排序的特点

1. 稳定性：冒泡排序是稳定的，因为在相等元素的情况下，它们的相对顺序不会改变。
2. 适用场景：适用于小规模数据集的排序，但对于大规模数据集，性能较低。
3. 逐步优化：可以通过标志变量减少不必要的比较，提高效率。

---

六、冒泡排序的优点

1. 概念简单，容易实现；
2. 稳定性强，适用于对数据稳定性要求较高的场景；
3. 适用于少量数据，尤其是数据基本有序的情况时，优化后的冒泡排序能减少不必要的比较，提高排序效率。

---

七、冒泡排序的缺点

1. 时间复杂度较高，最坏情况下为 O(n2)O(n^2)O(n2)，不适用于大规模数据集；
2. 数据交换次数多，即使数据部分有序，也需要进行较多的交换操作；
3. 在许多情况下效率低于插入排序、选择排序等简单排序算法。

---

示例代码（Python 实现）

1. 基础冒泡排序实现

def bubble_sort(arr):n = len(arr)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# 测试
arr1 = [5, 2, 9, 1, 5, 6]
print(bubble_sort(arr1))  # 输出：[1, 2, 5, 5, 6, 9]

2. 冒泡排序优化（减少不必要的比较）

def optimized_bubble_sort(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 = Trueif not swapped:break  # 如果本轮没有交换，说明已经排序完成return arr# 测试
arr2 = [1, 2, 3, 4, 5, 6]
print(optimized_bubble_sort(arr2))  # 输出：[1, 2, 3, 4, 5, 6]

3. 递归实现冒泡排序

def recursive_bubble_sort(arr, n=None):if n is None:n = len(arr)if n == 1:return arrfor i in range(n - 1):if arr[i] > arr[i + 1]:arr[i], arr[i + 1] = arr[i + 1], arr[i]return recursive_bubble_sort(arr, n - 1)# 测试
arr3 = [8, 3, 7, 4, 2, 9]
print(recursive_bubble_sort(arr3))  # 输出：[2, 3, 4, 7, 8, 9]

4. 处理带重复元素的冒泡排序

arr4 = [3, 1, 4, 1, 5, 9, 2, 6, 5]
print(optimized_bubble_sort(arr4))  # 输出：[1, 1, 2, 3, 4, 5, 5, 6, 9]

5. 逆序（降序）冒泡排序

def bubble_sort_desc(arr):n = len(arr)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# 测试
arr5 = [4, 2, 7, 1, 9, 3]
print(bubble_sort_desc(arr5))  # 输出：[9, 7, 4, 3, 2, 1]

---

结语

冒泡排序虽然简单，但由于效率较低，在大规模数据场景下并不推荐使用。优化后的冒泡排序能减少不必要的比较，提高性能，但仍然不如快速排序、归并排序等高级排序算法适合大规模数据排序。