此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
把元素排好序
- 排序(sorting)把列表排成有序的,通常是从小到大。
- 关键动作是交换(swap):把两个元素互换位置。
- 在 Python 里:
a[i], a[j] = a[j], a[i]一行就能交换两个列表元素。
冒泡排序
- 比较每一对相邻元素;如果顺序不对就交换它们。
- 完整跑一遍之后,最大的元素就"冒泡"到了末尾。
- 重复遍历过程。经过
n − 1次遍历后列表肯定已排序;如果某次遍历没有进行交换,可以提前停止。
English
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
插入排序
- 把列表左边的部分看作已经排好序。
- 取下一个元素,把它向左滑动,直到它落在正确的位置。
- 就像把手里的扑克牌一张一张地理顺。
English
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
比较两者
- 两者大约都要检查
n × n对元素,所以在大列表上都很慢。 - 当列表几乎已经有序时,插入排序很快。
- 还有更快的方法,但冒泡和插入排序容易理解。
用剑桥伪代码表示
- 冒泡排序,在数组
list[1:n]上使用一个名为temp的变量来标记是否发生了交换。
FOR i ← 1 TO n - 1
FOR j ← 1 TO n - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
常见错误
- 冒泡排序和插入排序都是 O(n²)。
- 手动追踪一个小列表,检查你的排序是否正确。
现在轮到你
- 每个任务都就地修改列表 —— 不需要返回它。
- 按检查答案来测试你的代码。
探索
看排序的过程
排序不断比较、交换,直到全部有序。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
编写 swap(items, i, j),交换列表中索引 i 和索引 j 处的元素。就地修改列表(不返回)。
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
编写 bubble_sort(items),用冒泡排序把列表排成升序。就地修改列表。
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
编写 insertion_sort(items),用插入排序把列表排成升序。就地修改列表。
点击“运行”查看此处输出。