要解决什么问题
给定一个整数序列,返回按升序排列的新序列,同时保留所有重复元素,不修改输入。
例如,输入 [7, 3, 8, 2, 5, 1],输出应为 [1, 2, 3, 5, 7, 8]。空序列、单个元素、负数和重复值也属于正常输入。
相邻交换为什么有效
从左到右比较相邻元素。如果左侧元素更大,就交换它们。一次完整扫描结束后,当前范围内的最大元素一定到达最右端。
原因在于:扫描每向右移动一步,已遇到元素中的最大值就会留在当前比较位置的右侧。把这个判断重复到范围末尾,就得到一次扫描的结论。
循环不变式
完成一轮扫描后,右侧已有一个元素就位。下一轮不必再次比较这个位置。
完成第 轮后,右侧 个位置已经按最终顺序排列。剩余工作只发生在左侧未完成的范围中。
这就是循环不变式的作用:它说明每一轮开始时已知什么,以及本轮如何推进问题。
看一次具体执行
下面的演示每次只执行一次比较。观察数值最大的元素如何逐步移动到右侧:
Bubble sort / one comparison at a time
演示达到排序完成状态后,可以点击 Reset 重新观察。尝试解释每次交换的原因,比只看最终数组更有帮助。
Python 实现与边界验证
下面的代码先复制输入,再逐轮缩小比较范围。如果某轮没有交换,说明序列已经有序,可以提前结束。
Bubble sort example
PythonYour output will appear here.
示例包含五种输入,并用 Python 内置排序结果作对照。这里的断言用于验证这份教学实现,不代表已经覆盖所有可能的输入类型。
| 输入 | 预期输出 | 检查目的 |
|---|---|---|
[] | [] | 空序列 |
[1] | [1] | 单个元素 |
[2, 2, 1] | [1, 2, 2] | 重复值不丢失 |
[-1, 3, 0] | [-1, 0, 3] | 负数比较 |
复杂度与适用范围
最坏情况下,需要比较:
因此最坏时间复杂度是 。由于这份实现复制了输入,额外空间是 ;不能把它称为原地排序实现。
提前退出让已经有序的输入只需一轮比较。教学示例适合观察算法结构;实际项目中,普通排序优先使用语言提供的成熟实现。
接下来怎么练习
先把输入改成倒序数组,再手动预测第一轮结束时的状态。随后试着把“循环不变式”写成一句可以在每轮开始时检查的描述。
如果想讨论如何缩小问题,可以继续阅读随想示例。