← Back to the notebookVEINSURE / WRITING

Technical Articles

技术文章示例:用冒泡排序理解循环不变式

从相邻交换、循环不变式和边界情况出发,写出可以验证的冒泡排序,并在浏览器中运行 Python 示例。

要解决什么问题

给定一个整数序列,返回按升序排列的新序列,同时保留所有重复元素,不修改输入。

例如,输入 [7, 3, 8, 2, 5, 1],输出应为 [1, 2, 3, 5, 7, 8]。空序列、单个元素、负数和重复值也属于正常输入。

相邻交换为什么有效

从左到右比较相邻元素。如果左侧元素更大,就交换它们。一次完整扫描结束后,当前范围内的最大元素一定到达最右端。

原因在于:扫描每向右移动一步,已遇到元素中的最大值就会留在当前比较位置的右侧。把这个判断重复到范围末尾,就得到一次扫描的结论。

循环不变式

完成一轮扫描后,右侧已有一个元素就位。下一轮不必再次比较这个位置。

完成第 kk 轮后,右侧 kk 个位置已经按最终顺序排列。剩余工作只发生在左侧未完成的范围中。

这就是循环不变式的作用:它说明每一轮开始时已知什么,以及本轮如何推进问题。

看一次具体执行

下面的演示每次只执行一次比较。观察数值最大的元素如何逐步移动到右侧:

Bubble sort / one comparison at a time

演示达到排序完成状态后,可以点击 Reset 重新观察。尝试解释每次交换的原因,比只看最终数组更有帮助。

Python 实现与边界验证

下面的代码先复制输入,再逐轮缩小比较范围。如果某轮没有交换,说明序列已经有序,可以提前结束。

Bubble sort example

Python
OUTPUTLoading editor…

Your output will appear here.

Runs locally in your browser · Pyodide 0.26.4 · 10s execution limit · 64 KiB output

示例包含五种输入,并用 Python 内置排序结果作对照。这里的断言用于验证这份教学实现,不代表已经覆盖所有可能的输入类型。

输入预期输出检查目的
[][]空序列
[1][1]单个元素
[2, 2, 1][1, 2, 2]重复值不丢失
[-1, 3, 0][-1, 0, 3]负数比较

复杂度与适用范围

最坏情况下,需要比较:

(n−1)+(n−2)+⋯+1=n(n−1)2(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}

因此最坏时间复杂度是 O(n2)O(n^2)。由于这份实现复制了输入,额外空间是 O(n)O(n);不能把它称为原地排序实现。

提前退出让已经有序的输入只需一轮比较。教学示例适合观察算法结构;实际项目中,普通排序优先使用语言提供的成熟实现。

接下来怎么练习

先把输入改成倒序数组,再手动预测第一轮结束时的状态。随后试着把“循环不变式”写成一句可以在每轮开始时检查的描述。

如果想讨论如何缩小问题,可以继续阅读随想示例。

END OF NOTEBack to top ↑

Search the notebook

Search published writing. Use ↑ ↓ to select, Enter to open.