经典排序算法 – 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，比较相邻的元素，如果它们的顺序错误就交换它们的位置。这个过程会不断重复，直到整个数列有序为止。由于每一轮比较后，最大的元素会被“冒泡”到数组的末尾，因此得名 冒泡排序。

1. 冒泡排序的基本思路

冒泡排序的基本思路是：

  • 从左到右依次比较相邻的两个元素，如果前一个元素比后一个元素大，就交换它们的位置。
  • 每次遍历都会将当前未排序部分的最大元素“冒泡”到序列的末端。
  • 重复上述过程，直到没有需要交换的元素为止，此时序列已排序完成。

2. 冒泡排序的算法步骤

  1. 从头到尾遍历列表，依次比较相邻的两个元素。
  2. 如果当前元素大于下一个元素，则交换它们的位置。
  3. 经过一轮遍历后，最大的元素会被“冒泡”到列表的最后。
  4. 重复以上步骤，每次遍历的范围逐渐减小，因为每轮排序都会把当前未排序部分中的最大元素放到已排序部分的末尾。
  5. 直到没有发生交换，排序结束。

3. 冒泡排序的时间复杂度

  • 最坏时间复杂度：O(n^2)，当数组是倒序排列时，每一轮都需要进行大量的交换。
  • 最好时间复杂度：O(n)，如果数组已经是有序的，冒泡排序只需要进行一次遍历即可。
  • 平均时间复杂度：O(n^2)，在大多数情况下，平均时间复杂度为二次方级别。
  • 空间复杂度：O(1)，冒泡排序是原地排序算法，不需要额外的存储空间。

4. 冒泡排序的代码实现

下面是一个用 Python 实现的冒泡排序算法：

def bubble_sort(arr):
    n = len(arr)
    # 外层循环，控制所有的遍历次数
    for i in range(n):
        swapped = False
        # 内层循环，进行相邻元素的比较和交换
        for j in range(0, n - i - 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

# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("排序后的数组:", sorted_arr)

代码解释：

  • n 是数组的长度。
  • 外层循环：控制排序的轮次，每轮会把最大的元素移到末尾。
  • 内层循环：进行相邻元素的比较与交换，每一轮会比前面小的部分。
  • 优化：加入 swapped 标记，如果某一轮没有发生交换，说明数组已经有序，可以提前终止循环。

5. 冒泡排序的优缺点

优点：

  • 简单易懂：算法实现简单，适合初学者学习和理解。
  • 稳定排序：冒泡排序是一种稳定的排序算法，即相等的元素不会交换位置，保证相等元素的顺序不变。

缺点：

  • 效率低下：由于每轮排序只会把一个元素放到最终位置，所以最坏情况下时间复杂度为 O(n^2)，对大规模数据排序时效率很低。
  • 不适合大规模数据：冒泡排序不适合处理大数据量的排序问题，因为它的时间复杂度较高。

6. 冒泡排序的变种

除了常规的冒泡排序，还有一些优化和变种，最常见的包括：

(1) 双向冒泡排序（Cocktail Shaker Sort）

双向冒泡排序是一种改进版的冒泡排序，它不仅从左到右进行比较，还从右到左进行比较。通过这种双向的方式，可以更快地把最大和最小元素移动到序列的两端。

(2) 冒泡排序优化（提前退出）

如果某一轮遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序，从而减少不必要的遍历。

7. 总结

冒泡排序是一种基础的排序算法，虽然时间复杂度较高，不适合处理大规模数据，但其简单易懂的原理和实现方式，使其成为学习排序算法的经典案例。它的稳定性和优化方法（如提前退出）使其在某些小规模数据集上仍然有其应用价值。