| English | 释义 | 拼音 |
|---|---|---|
| bubble sort/ˈbʌbl sɔːt/ | 冒泡排序 | mào pào pái xù |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | 插入排序 | chā rù pái xù |
| in place/ɪn pleɪs/ | 原地 | yuán dì |
| stable/ˈsteɪbl/ | 稳定 | wěn dìng |
故意很慢的排序
- 每个正经的库都用一种考试不会要求你写的算法排序。冒泡排序和插入排序都是 $O(n^2)$,在大列表上都会被任何像样的排序算法击败。
- 它们仍然在大纲上,而且理由充分:它们短到可以用手追踪,而追踪一遍正是你学会排序对数组做了什么的方式。
- 插入排序也确有真实的用武之地。在小的、或已经接近有序的列表上,它确实是最快的东西,真实的库正是在这些情形下切换到它。
- 这一课讲冒泡排序(bubble sort)和插入排序(insertion sort):算法、它们的表现,以及各自在哪里取胜。
冒泡排序
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
ENDIF
NEXT i
IF NOT swapped THEN // 已经有序
EXIT FOR
ENDIF
NEXT pass
- 每一遍比较相邻的对并交换顺序错误的,于是剩余的最大值"冒"到末尾。
- 第 $k$ 遍之后,最后 $k$ 个元素已经就位,这就是内层循环停在 $n - \text{pass}$ 的原因。
swapped标志让它能提前结束:如果整整一遍没有交换,列表就已经有序。
插入排序
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j] // 右移
j ← j - 1
ENDWHILE
A[j + 1] ← key // 放进去
NEXT i
- 它在前面构建一个有序段,每次增长一个。每个新元素被取出存为
key,更大的元素右移让出空位,再把 key 放进去。 - 大多数人整理一手扑克牌就是这样做的,而这正是考试期待的类比。

左边有序,右边未动,边界不断右移
排序算法
compare adjacent, swap if needed
Step through a bubble sort: each pass floats the largest value to the end.
Bubble sort works by:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
The average/worst-case time complexity of bubble sort is:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit.
例题:追踪一遍
- 追踪对 5, 3, 8, 1 做冒泡排序的第一遍。
- 比较 5 和 3:顺序错误,交换,得到 3, 5, 8, 1。比较 5 和 8:顺序正确,不交换。比较 8 和 1:交换,得到 3, 5, 1, 8。
- 一遍之后最大值 8 已在它的最终位置,此后每一遍都可以少比较一次。
- 现在追踪对 3, 5, 8, 1 做插入排序的第三步。 key 是 1。把 8、5、3 各右移一位,再把 1 放到最前:1, 3, 5, 8。每一步之后都要写出数组;分数就在那里。
Insertion sort builds the sorted result by:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place.
How does insertion sort place each new element?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps.
性能
| 冒泡 | 插入 | |
|---|---|---|
| 最好情况 | $O(n)$,一遍没有交换 | $O(n)$,已经有序,不需移动 |
| 平均和最坏 | $O(n^2)$ | $O(n^2)$ |
| 额外内存 | $O(1)$,原地(in place) | $O(1)$,原地 |
| 稳定性 | 是 | 是,稳定(stable) |
- 原地意味着它只需常数量的额外内存,在数组内部完成排序。稳定意味着两个相等的值保持原来的相对顺序,当列表已按另一个字段排过序时这很要紧。
- 两者在已有序的数据上都能达到 $O(n)$,但冒泡排序必须带
swapped标志才行。没有它,它总是把每一遍都走完。
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
5 and 3 swap, 5 and 8 do not, 8 and 1 swap. The largest value has reached the end, so the next pass can be one comparison shorter.
例题:选哪种排序,为什么
- 20 万条记录必须从头排序。 两种都不选:它们都是 $O(n^2)$,需要 $O(n \log n)$ 的归并排序或快速排序。要说出这一点,而不是从两个差的里挑一个不那么差的。
- 一个有 1 万条记录的有序列表在末尾新增了 5 条,必须重新排序。 插入排序:数据接近有序,所以每个新 key 只移动很短的距离,接近 $O(n)$。
- 一个教学例子必须在纸上用手追踪。 冒泡排序:它最容易跟着走,这正是它如今真正剩下的用途。
- 从数据的状态和规模来论证,而不是从一般偏好。
Match each sorting idea to what it means.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs.
Which are true of both bubble sort and insertion sort? Select 所有 that apply.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
On a large unsorted list an O(n log n) sort wins decisively. Saying so is the right answer, not choosing the least bad of the two.
为什么一趟说明不了全部
- 两种排序都要反复扫描,而考试区分它们靠的是一趟做成了什么,以及什么时候停下来。
- 冒泡排序的一趟比较相邻的两个并交换,所以一趟把剩下最大的那个送到它的最终位置。整个排序要 $n - 1$ 趟。
- 插入排序的一趟取下一个元素,把它往回插入已排好的那部分,所以 $k$ 趟之后前 $k$ 个元素彼此之间有序,但还不在最终位置上。
- 冒泡排序可以用一个标志位改进:若某一趟没有发生交换,说明列表已经有序,算法就停下。对接近有序的数据,这会让它变成一趟。
- 没有那个标志位时,两者最坏情况都是 $n^2$,这就是它们对大文件都不是好选择、而考试只问小规模的原因。
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason.
Match each sort to what one pass achieves.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
That difference is what a trace question is really testing. A bubble-sort flag also lets it stop early on nearly-sorted data, which insertion sort handles well anyway.
容易丢掉的分
- 冒泡排序比较的是相邻的对。把一个元素与其余所有元素比较的答案描述的是另一种算法。
- 内层循环每遍都变短,因为数组末尾已经就位。要说出原因。
- 插入排序把元素右移以让出空位;它不是反复交换。这个区别正是这个算法的要点。
- 两者在平均和最坏情况下都是 $O(n^2)$,最好情况是 $O(n)$。给出复杂度时要带上情形。
你掌握了
- 冒泡排序:反复遍历,比较相邻对并交换,最大值冒到末尾,内层循环每遍变短,用
swapped标志提前退出 - 插入排序:在前面扩大有序段,把每个 key 取出、把更大的元素右移、再把 key 放进空位
- 两者平均和最坏都是 $O(n^2)$,最好是 $O(n)$,都是原地且稳定的
- 插入排序在小的或接近有序的列表上确有优势;对大型无序列表,两者都不是正确答案