波仔
⌨️ 第四章 流程图与算法
📄 一句话概括

冒泡排序：相邻两个比一比、大的往右换，每一轮【最大的泡泡】沉到队尾；摇晃排序（Shaker Sort，又称鸡尾酒排序、双向冒泡）：冒泡的改良——来回双向扫，对【基本有序】的数据快得多。

📝 本节和前面几节的关系

4-11 的选择／插入是【挑与插】，这一对的灵魂是【相邻交换】。回收 4-11 的 O(n²) 与【基本有序】话题——摇晃排序正是冲着这个短板来的改良。

一、冒泡：相邻交换、大的沉底

[5, 3, 8, 1, 9, 2]  从左往右逐对比较、大的往右换
第一轮：5>3 换 -> 3,5,8...；8>1 换 -> 9 沉底 ...
第一轮结束：9 已在最右（最大的泡泡先浮出）
第二轮：对剩下前 5 个再来一遍 -> 8 沉到倒数第二 ...

b = [5, 3, 8, 1, 9, 2]
for i in range(len(b) - 1):            # 共 n-1 轮
    swapped = False
    for j in range(len(b) - 1 - i):    # 每轮少比一个（尾部已就位）
        if b[j] > b[j + 1]:
            b[j], b[j + 1] = b[j + 1], b[j]
            swapped = True
    if not swapped:                    # 整轮没换过 = 已经有序，提前收工
        break
print(b)                               # [1, 2, 3, 5, 8, 9]

两个标配优化：每轮缩短比较范围（尾部已排好）＋ swapped 标志（没换就提前停）。加上后者，冒泡对【已有序】数据是 O(n)；乱数据仍是最坏 O(n²)。

二、摇晃排序：来回双向扫

冒泡的盲区：小的沉不下来——每轮只保证大的往右挪，左边的小乌龟（如最后的 1）每次只能挪一格。摇晃排序（Shaker／鸡尾酒／双向冒泡）一轮干两件事：先从左往右冒（大数沉底），再从右往左扫（小数浮头）——乌龟坐上回程快车：

[2, 3, 4, 5, 1]  只有 1 错位
冒泡：要 4 轮（1 每轮挪一格）
摇晃：第 1 轮正向（5 沉底）＋反向（1 一次漂到最左）——1~2 轮搞定

c = [2, 3, 4, 5, 1]
lo, hi = 0, len(c) - 1
while lo < hi:
    swapped = False
    for j in range(lo, hi):            # 正向：大的沉底
        if c[j] > c[j + 1]:
            c[j], c[j + 1] = c[j + 1], c[j]
            swapped = True
    hi -= 1
    for j in range(hi, lo, -1):        # 反向：小的浮头
        if c[j] < c[j - 1]:
            c[j], c[j - 1] = c[j - 1], c[j]
            swapped = True
    lo += 1
    if not swapped:
        break
print(c)                               # [1, 2, 3, 4, 5]

性格：最坏仍 O(n²)，两端夹击使扫描区间双向收缩——对【部分有序】数据轮数减半以上；代码复杂度比冒泡高一档，实战性价比一般，但【改良思路】极经典。

三、动手 Demo：乌龟现形

def bubble(arr):
    b = arr.copy()
    for i in range(len(b) - 1):
        for j in range(len(b) - 1 - i):
            if b[j] > b[j + 1]:
                b[j], b[j + 1] = b[j + 1], b[j]
    return b

data = [2, 3, 4, 5, 1]
print(bubble(data))    # [1, 2, 3, 4, 5] —— 结果一样

读结果：结果与摇晃排序相同——差别在过程：冒泡的 1 要走 4 格（每轮一格），摇晃的 1 一轮直达。拿 4-11 的插入排序比同一条数据：一次插入直接到位——三种算法、同一结果、路径各不同。

四、30 秒实验

在冒泡的内层循环里加一行 print(b)（每轮打印），拿 [2, 3, 4, 5, 1] 跑一遍——亲眼看 1 每轮只挪一格（乌龟）。这 30 秒的动画感，胜过文字十遍。

五、常见误区

  1. 【摇晃排序复杂度比冒泡低一个档次】——错。最坏仍是 O(n²)；它改良的是常数与【部分有序】场景的轮数，不是复杂度档位。
  2. 【加了 swapped 的冒泡就是 O(n)】——只对【已有序／基本有序】成立；乱数据照样两两比、O(n²)。
  3. 【这些 O(n²) 排序实际项目没人用】——半错。直接手写确实少（Python 用 sorted）；但小数据、教学、嵌入式极端受限环境里它们仍出场，且是理解 4-13 高速排序的地基。
自测三问（点开对答案） 1. **冒泡排序每轮结束能保证什么？** 答：当前未排序段的最大值沉到段尾——每轮至少【钉死】一个元素的最终位置。 2. **摇晃排序改良了冒泡的什么短板？** 答：小元素（乌龟）每轮只能挪一格的问题——反向扫描让小数一次漂到最左，双向收缩区间。 3. **swapped 标志的作用？** 答：整轮无交换说明已有序，提前退出——对已有序数据从 O(n²) 降到 O(n)。

相关笔记