Sorting algorithms · 排序算法
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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 |
The sort that is slow on purpose
- Every serious library sorts with an algorithm no exam asks you to write. Bubble sort and insertion sort are both $O(n^2)$, and both are beaten by any decent sort on a large list.
- They are on the syllabus anyway, and for a good reason: they are short enough to trace by hand, and tracing one is how you learn what a sort actually does to an array.
- There is also a real case for insertion sort. On a list that is small, or already nearly sorted, it is genuinely the fastest thing there is, and real libraries switch to it for exactly those cases.
- This lesson is bubble sort 冒泡排序 and insertion sort 插入排序: the algorithms, their behaviour, and where each one wins.
故意很慢的排序
- 每个正经的库都用一种考试不会要求你写的算法排序。冒泡排序和插入排序都是 $O(n^2)$,在大列表上都会被任何像样的排序算法击败。
- 它们仍然在大纲上,而且理由充分:它们短到可以用手追踪,而追踪一遍正是你学会排序对数组做了什么的方式。
- 插入排序也确有真实的用武之地。在小的、或已经接近有序的列表上,它确实是最快的东西,真实的库正是在这些情形下切换到它。
- 这一课讲冒泡排序(bubble sort)和插入排序(insertion sort):算法、它们的表现,以及各自在哪里取胜。
Bubble sort
- Each pass compares adjacent pairs and swaps any that are out of order, so the largest remaining value "bubbles" to the end.
- After pass $k$ the last $k$ elements are final, which is why the inner loop stops at $n - \text{pass}$.
- The
swappedflag lets it stop early: if a whole pass makes no swap, the list is sorted.
冒泡排序
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标志让它能提前结束:如果整整一遍没有交换,列表就已经有序。
Insertion sort
- It builds a sorted section at the front, growing by one each time. Each new element is held aside as
key, larger elements are shifted right to open a gap, and the key is dropped in. - This is how most people sort a hand of playing cards, which is the analogy the exam expects.
The left is sorted, the right is untouched, and the boundary moves right
插入排序
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 放进去。 - 大多数人整理一手扑克牌就是这样做的,而这正是考试期待的类比。
左边有序,右边未动,边界不断右移
Sorting algorithms · 排序算法
compare adjacent, swap if needed · 比较相邻的,如需要就交换
Step through a bubble sort: each pass floats the largest value to the end. · 逐步走过一个冒泡排序:每遍把最大的值浮到末尾。
Bubble sort works by: · 冒泡排序这样工作:
Each pass swaps adjacent pairs, "bubbling" the largest element to the end. · 每遍交换相邻对,把最大的元素“冒泡”到末尾。
The average/worst-case time complexity of bubble sort is: · 冒泡排序的平均/最坏情况时间复杂度是:
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit. · 在 n 个元素上的两个嵌套循环给出 O(n²);最好情况(已排序)带提早退出是 O(n)。
Worked example: trace one pass
- Trace the first pass of a bubble sort on 5, 3, 8, 1.
- Compare 5 and 3: out of order, swap, giving 3, 5, 8, 1. Compare 5 and 8: in order, no swap. Compare 8 and 1: swap, giving 3, 5, 1, 8.
- After one pass the largest value, 8, is in its final position, and one more comparison per pass can be skipped from now on.
- Now trace insertion sort's third step on 3, 5, 8, 1. The key is 1. Shift 8, 5 and 3 each one place right, then place 1 at the front: 1, 3, 5, 8. Show the array after every step; that is where the marks are.
例题:追踪一遍
- 追踪对 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: · 插入排序这样构建排序的结果:
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? · 插入排序怎样放置每个新元素?
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps. · 把 key 取出并右移,正是它与冒泡排序反复相邻交换的区别所在。
Performance
| bubble | insertion | |
|---|---|---|
| best case | $O(n)$, one pass with no swaps | $O(n)$, already sorted, no shifts |
| average and worst | $O(n^2)$ | $O(n^2)$ |
| extra memory | $O(1)$, in place 原地 | $O(1)$, in place |
| stable | yes | yes, stable 稳定 |
- In place means it needs only a constant amount of extra memory, sorting within the array itself. Stable means two equal values keep their original relative order, which matters when a list has already been sorted by another field.
- Both reach $O(n)$ on already-sorted data, but only if bubble sort has the
swappedflag. Without it, it always performs every pass.
性能
| 冒泡 | 插入 | |
|---|---|---|
| 最好情况 | $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. · 对 5, 3, 8, 1 做冒泡排序的第一遍之后,数组是什么?用逗号分隔写出四个数。
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. · 5 和 3 交换,5 和 8 不换,8 和 1 交换。最大值已到末尾,所以下一遍可以少比较一次。
Worked example: which sort, and why
- A list of 200,000 records must be sorted from scratch. Neither: both are $O(n^2)$, so a merge or quick sort at $O(n \log n)$ is needed. Say so rather than choosing the least bad.
- A sorted list of 10,000 gains 5 new records at the end and must be sorted again. Insertion sort: the data is nearly sorted, so each new key shifts only a short distance and it approaches $O(n)$.
- A teaching example must be traced by hand on paper. Bubble sort: it is the simplest to follow, which is its real remaining use.
- Justify from the state of the data and the size, not from a general preference.
例题:选哪种排序,为什么
- 20 万条记录必须从头排序。 两种都不选:它们都是 $O(n^2)$,需要 $O(n \log n)$ 的归并排序或快速排序。要说出这一点,而不是从两个差的里挑一个不那么差的。
- 一个有 1 万条记录的有序列表在末尾新增了 5 条,必须重新排序。 插入排序:数据接近有序,所以每个新 key 只移动很短的距离,接近 $O(n)$。
- 一个教学例子必须在纸上用手追踪。 冒泡排序:它最容易跟着走,这正是它如今真正剩下的用途。
- 从数据的状态和规模来论证,而不是从一般偏好。
Match each sorting idea to what it means. · 把每个排序想法与它的含义配对。
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order. · 冒泡交换邻居,插入增长一个已排序的前缀;两者最坏情况都是 O(n²);稳定性是关于相等键的顺序。
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted. · 插入排序在小的或几乎排序的数组上运行接近 O(n),因为很少的元素需要被移动。
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 all · 所有 that apply. · 关于冒泡排序和插入排序,哪些对两者都成立?选出所有适用的。
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. · 在大型无序列表上,O(n log n) 的排序有压倒性优势。说出这一点才是正确答案,而不是从两者中挑不那么差的。
Why one pass is not the whole story
- Both sorts do repeated passes, and the exam distinguishes them by what one pass achieves and by when they stop.
- A bubble sort pass compares adjacent pairs and swaps them, so one pass carries the largest remaining item to its final place. The whole sort is $n - 1$ passes.
- An insertion sort pass takes the next item and moves it back into the already-sorted part, so after $k$ passes the first $k$ items are sorted among themselves but not yet in final position.
- Bubble sort can be improved with a flag: if a pass makes no swaps, the list is already sorted and the algorithm stops. On nearly-sorted data that turns it into one pass.
- Without the flag, both are $n^2$ in the worst case, which is why either is a poor choice for a large file and why the exam asks about small ones.
为什么一趟说明不了全部
- 两种排序都要反复扫描,而考试区分它们靠的是一趟做成了什么,以及什么时候停下来。
- 冒泡排序的一趟比较相邻的两个并交换,所以一趟把剩下最大的那个送到它的最终位置。整个排序要 $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 条。重新排序适合用哪种?
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason. · 接近有序的数据正是插入排序的最好情况,接近 O(n)。真实的库正是因此切换到它。
Match each sort to what one pass achieves. · 把每种排序与它一趟所完成的事配对。
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. · 这个差别正是追踪题真正在考的。冒泡排序的标志位还能让它在接近有序的数据上提前停止,而插入排序本来就擅长这种数据。
Marks that slip away
- Bubble sort compares adjacent pairs. An answer that compares an element with all the others is describing a different algorithm.
- The inner loop shortens each pass, because the end of the array is already final. Say why.
- Insertion sort shifts elements right to open a gap; it does not swap repeatedly. The distinction is the point of the algorithm.
- Both are $O(n^2)$ on average and at worst, and $O(n)$ at best. Give the case with the order.
容易丢掉的分
- 冒泡排序比较的是相邻的对。把一个元素与其余所有元素比较的答案描述的是另一种算法。
- 内层循环每遍都变短,因为数组末尾已经就位。要说出原因。
- 插入排序把元素右移以让出空位;它不是反复交换。这个区别正是这个算法的要点。
- 两者在平均和最坏情况下都是 $O(n^2)$,最好情况是 $O(n)$。给出复杂度时要带上情形。
You've got it
- bubble sort: repeated passes comparing adjacent pairs and swapping, largest bubbling to the end, inner loop shortening each pass, with a
swappedflag for early exit - insertion sort: grow a sorted section at the front, holding each key aside, shifting larger elements right and dropping the key into the gap
- both are $O(n^2)$ average and worst, $O(n)$ best, in place and stable
- insertion sort genuinely wins on small or nearly sorted lists; for a large unsorted list neither is the right answer
你掌握了
- 冒泡排序:反复遍历,比较相邻对并交换,最大值冒到末尾,内层循环每遍变短,用
swapped标志提前退出 - 插入排序:在前面扩大有序段,把每个 key 取出、把更大的元素右移、再把 key 放进空位
- 两者平均和最坏都是 $O(n^2)$,最好是 $O(n)$,都是原地且稳定的
- 插入排序在小的或接近有序的列表上确有优势;对大型无序列表,两者都不是正确答案