Sorting · 排序
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 此页面需较新浏览器（支持 SharedArrayBuffer）。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
English
Putting items in order
- Sorting arranges a list into order, usually smallest first.
- The key move is a swap: exchange two items.
- In Python:
a[i], a[j] = a[j], a[i]swaps two list items in one line.
中文
把元素排好序
- 排序(sorting)把列表排成有序的,通常是从小到大。
- 关键动作是交换(swap):把两个元素互换位置。
- 在 Python 里:
a[i], a[j] = a[j], a[i]一行就能交换两个列表元素。
English
Bubble sort
- Compare each pair of neighbours; swap them if they are out of order.
- After one full pass, the largest item has "bubbled" to the end.
- Repeat the passes until no swaps are needed.
中文
冒泡排序
- 比较每一对相邻元素;如果顺序不对就交换它们。
- 完整跑一遍之后,最大的元素就"冒泡"到了末尾。
- 重复这些遍,直到不再需要任何交换。
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
Insertion sort
- Treat the left part of the list as already sorted.
- Take the next item and slide it left until it sits in the right place.
- Like sorting playing cards in your hand, one at a time.
中文
插入排序
- 把列表左边的部分看作已经排好序。
- 取下一个元素,把它向左滑动,直到它落在正确的位置。
- 就像把手里的扑克牌一张一张地理顺。
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)
English
Compare them
- Both check roughly
n × npairs, so both are slow on big lists. - Insertion sort is fast when the list is almost sorted already.
- Faster methods exist, but bubble and insertion are easy to understand.
中文
比较两者
- 两者大约都要检查
n × n对元素,所以在大列表上都很慢。 - 当列表几乎已经有序时,插入排序很快。
- 还有更快的方法,但冒泡和插入排序容易理解。
English
In Cambridge pseudocode
- Bubble sort with a
tempvariable for the swap.
中文
用剑桥伪代码表示
- 用一个
temp变量来完成交换的冒泡排序。
FOR i ← 0 TO LENGTH(list) - 2
FOR j ← 0 TO LENGTH(list) - 2 - 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
English
Common mistakes
- Bubble and insertion sort are both O(n²).
- Trace a small list by hand to check your sort works.
中文
常见错误
- 冒泡排序和插入排序都是 O(n²)。
- 手动追踪一个小列表,检查你的排序是否正确。
English
Now you try
- Each task changes the list in place — no need to return it.
- Press Check answer to test your code.
中文
现在轮到你
- 每个任务都就地修改列表 —— 不需要返回它。
- 按检查答案来测试你的代码。
Explore · 探索
Watch a sort run · 看排序的过程
Sorting repeatedly compares and swaps until everything is in order. · 排序不断比较、交换,直到全部有序。
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return). · 编写 swap(items, i, j),交换列表中索引 i 和索引 j 处的元素。就地修改列表(不返回)。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place. · 编写 bubble_sort(items),用冒泡排序把列表排成升序。就地修改列表。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place. · 编写 insertion_sort(items),用插入排序把列表排成升序。就地修改列表。
Click Run to see the output here. · 点击“运行”查看此处输出。