Sorting
Python for A-Level CS Lesson 8 2:02 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Bubble sort only ever looks at neighbours.
冒泡排序永远只看相邻的两个。
Walk the list and compare each pair in turn, swapping any that are the wrong way round.
遍历列表，依次比较每一对，顺序反了就交换。
Watch the five: compared, moved, compared again, and by the end of the pass it has bubbled to the end of the list.
看着那个 5：被比较、被移动、又被比较， 到这一趟结束时，它已经浮到了列表的末尾。
Repeat the pass and the next largest follows it.
再来一趟，第二大的就跟着到位。
Insertion sort works the way people sort cards.
插入排序的做法，就是人整理扑克牌的做法。
Treat the left part of the list as already in order.
把列表左边那一段当作已经有序的。
Take the next one and call it the key.
取下一个，把它叫做 key。
Then slide the bigger sorted items right, one at a time, until the key slides into place in the gap they left.
然后把有序部分里比它大的元素依次往右挪， 直到 key 滑进它们让出的那个空位。
The sorted part has grown by one, and you repeat.
有序部分长了一个，然后重复。
On a jumbled list both are n squared, and neither is a good choice for a big one.
在一个乱序的列表上，两者都是 O(n²)， 对于大列表来说，谁都不是好选择。
But look at the second row: when the list is almost sorted already, insertion sort is close to n — much faster — and bubble sort is not.
但看第二行：当列表本来就接近有序时， 插入排序接近 O(n)——快得多——而冒泡排序不是。
The reason is in the code you just saw: insertion sort's inner loop stops as soon as the key fits, and on nearly-sorted data it stops immediately.
原因就在你刚看到的代码里： 插入排序的内层循环一旦发现 key 已经放得下就立刻停下， 而在接近有序的数据上，它几乎立刻就停。
The first task is the swap both sorts are built on.
第一道题就是两种排序都依赖的那个交换。
Python does it in one line; the exam wants the three-line version with a temporary.
Python 一行就能做到；考卷要的是带临时变量的三行版本。
And note what all three tasks say: in place.
再注意这三道题都说了一句话：原地（in place）。
That means you change the caller's list itself and return nothing — the same idea as pass-by-reference, and the reason the checker looks at the list rather than a return value.
意思是你直接改动调用者那个列表本身，什么都不返回—— 这和"按引用传递"是同一个概念， 也是为什么检查器看的是那个列表，而不是返回值。
Four things to take with you.
带走四点。
One: bubble sort compares neighbours, pass after pass.
第一：冒泡排序比较相邻元素，一趟接一趟。
Two: insertion sort slides each key into a sorted left side.
第二：插入排序把每个 key 滑进左边已排好的那一段。
Three: both are n squared on a jumbled list.
第三：在乱序列表上，两者都是 O(n²)。
Four: insertion is much faster when the list is almost sorted.
第四：当列表接近有序时，插入排序快得多。
Now do the three tasks.
现在去做那三道题。