冒泡排序

5.1 冒泡排序的定义

冒泡排序 (Bubble Sort) — 是个简单的排序算法， 它会多次遍历列表，比较相邻的元素，并在它们的顺序不对时交换它们的位置。这个 过程会持续进行，直到列表被完全排序。

工作原理：

1. 算法遍历列表，比较每一对相邻元素。
2. 如果元素顺序不对（对于升序排列来说，第一个比第二个大）— 交换它们。
3. 这个过程会为列表中的所有元素对重复。
4. 每次完整遍历后，最大的元素会“浮”到它该在的位置（就像气泡浮到水面），所以它不再参与 后续的遍历。
5. 这个过程会重复直到列表排序完成。

冒泡排序的时间和空间复杂度

时间复杂度：

• 最坏情况: O(n^2) — 当元素最初以相反顺序排列时发生。
• 平均情况: O(n^2) — 随机元素排列时发生。
• 最好情况: O(n) — 当元素已排序时发生 (算法可以为这种情况进行优化，通过加入检查，看看遍历过程中是否发生了元素交换)。

空间复杂度：

O(1) — 因为算法使用固定数量的额外内存（只有几个变量用于存储临时值）。

5.2 算法实现

冒泡排序算法是最简单、最原始的排序算法 列表/数组元素。它只是对元素进行两两比较，并在需要时交换它们。

版本 1：

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # 交换元素

print("排序后的数组:", array)
# 输出: 排序后的数组: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

内层循环（绿色突出）比较元素及其右边的元素。 如果需要，就交换这些元素。

版本 2：

立即可以在我们的算法中添加优化：第一次遍历后 最大的元素会在最右边出现，因此它可以在下一个循环中被忽略。

第二次迭代后，最右边将有两个最大元素，因此 内循环可以进行到 n - 1，而不是n - 1 - i。其中 i 是 外循环的已遍历迭代次数。

新版本会是这样的：

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # 交换元素

print("排序后的数组:", array)
# 输出: 排序后的数组: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

版本 3：

另外，数组可能已经几乎排序好了。因此可以添加 这样的优化：如果内循环遍历了所有元素但没有 进行任何交换，排序则完成。

在此版本中使用了变量swapped，它会跟踪在最后一次遍历过程中是否发生了元素交换。如果遍历数组后没有发生任何交换，这意味着数组已经排序了，进行进一步的迭代毫无意义 — 它们不会改善排序。因此，变量swapped使算法在几乎排序的数组上显著加速，提前结束它的执行。

在Python中实现冒泡排序：

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # 优化：检查是否发生了交换
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # 交换元素
                swapped = True
        if not swapped:
            break  # 如果没有交换，数组已经排序好
    return array

# 使用示例：
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("排序后的数组:", sorted_array)
# 输出: 排序后的数组: [11, 12, 22, 25, 34, 64, 90]