Searching & Sorting
A-Level Computer Science Topic 19 15:33 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A phone book with a million names.
一本有一百万个名字的电话簿。
If you check them one at a time, you might make a million comparisons.
如果你一个一个地查，可能要比较一百万次。
But you already know the trick: open it in the middle, decide which half the name is in, and throw the other half away.
但那个诀窍你其实早就知道：从中间翻开，判断名字在哪一半，然后把另一半整个扔掉。
Do that again and again, and a million names fall to about twenty questions.
一次又一次地这样做，一百万个名字就只剩下大约二十个问题。
Same data, same answer, fifty thousand times less work.
同样的数据、同样的答案，工作量却少了五万倍。
That is what choosing the right algorithm buys you.
这就是选对算法能带给你的东西。
Searching, sorting, and how we compare algorithms.
查找、排序，以及我们如何比较算法。
Today: linear and binary search, bubble and insertion sort, Big-O notation, and recursion with the call stack.
今天我们讲：线性查找与二分查找、冒泡排序与插入排序、 大O表示法，以及配合调用栈的递归。
Let's begin.
让我们开始吧。
A search finds a target value in a collection — often an array — and returns its position, or reports that it was not found.
查找是在一个集合——常常是一个数组——里找到一个目标值，并返回它的位置， 或者报告它不存在。
Searching a sorted list, like a phone book, is far faster than checking every entry one by one.
在一个有序的列表里查找，就像查电话簿一样， 要比一个一个地核对快得多。
Two standard algorithms do this job: linear search and binary search.
做这件事有两种标准算法：线性查找和二分查找。
The choice depends on whether the data is already sorted, how big it is, and how often you will search it.
选哪一种，取决于数据是否已经有序、规模有多大，以及你要查多少次。
Two ways to find something.
找一样东西有两种方式。
A linear search starts at the first item and walks along, comparing each one with the target, until it finds a match or runs out.
线性查找从第一个元素开始一路往下走，把每一个都和目标比较， 直到找到，或者走到头。
It needs no preparation, so it works on any list, sorted or not — but on a list of a thousand it may need a thousand comparisons.
它不需要任何准备，所以任何列表都能用，排没排序都行—— 但在一千个元素的列表上，它可能要比较一千次。
A binary search is smarter, though it demands a sorted list.
二分查找更聪明，不过它要求列表必须是有序的。
Look at the middle item; if the target is smaller, keep the left half, otherwise keep the right half.
看中间那个元素；如果目标更小，就留下左半边，否则留下右半边。
Every step throws away half of what is left, so a thousand items need at most ten comparisons.
每一步都扔掉剩下的一半，所以一千个元素最多只要比较十次。
Watch a linear search walk the list.
来看线性查找怎样走过列表。
It starts at the left and checks each cell against the target.
它从左边开始，把每一个格子都和目标比较。
The moment it finds a match it stops and returns that index.
一找到匹配就停下来，返回那个下标。
If it reaches the end with no match, it returns a special sentinel value — usually minus one — that means "not found".
如果走到末尾还没有匹配， 它就返回一个特殊的哨兵值——通常是负一——表示「未找到」。
The caller then tests whether the result equals minus one.
调用者再检查结果是否等于负一。
No sorting is required, so this is the right tool for unsorted data or for a very short list.
不需要排序， 所以对无序数据或很短的列表，这是正确的工具。
Here is a linear search on the alphabet, hunting for W.
这是在字母表上线性查找 W。
Cells A through V are checked in turn — that is twenty-three comparisons before the match.
从 A 到 V 的格子依次被检查—— 找到匹配前一共比较了二十三次。
Worst case is order n: the target sits at the end, or is missing entirely.
最坏情况是 n 阶：目标在末尾，或者根本不在。
Best case is just one comparison, when the target is first.
最好情况只要一次比较，目标就在最前面。
Average case sits in between.
平均情况介于两者之间。
Use linear search when the list is unsorted, or when n is small enough that the simple walk costs almost nothing.
当列表无序，或者 n 小到简单遍历几乎不花代价时，就用线性查找。
Watch it happen.
来看它是怎么运作的。
There is a low end, a high end, and the middle between them.
有一个下界、一个上界，以及它们中间的那个位置。
Compare the middle with the target: too small, and the low end jumps past it; too big, and the high end drops back.
把中间的元素和目标比较：中间的太小，下界就跳到它后面；中间的太大，上界就退回来。
The window shrinks by half every single time, so it closes on the answer in a handful of steps.
窗口每一次都缩小一半，所以只要几步就能锁定答案。
Just remember the price of that speed — the list must already be sorted.
只要记住这份速度的代价——列表必须事先就是有序的。
If you search only once, sorting first may not be worth it; if you search again and again, it always is.
如果你只查一次，先排序可能并不划算； 如果你要反复地查，那就一定划算。
The algorithm keeps three indexes: low, mid and high.
算法维护三个下标：下界、中点和上界。
Mid is the average of low and high, rounded down with integer division.
中点是下界与上界的平均值，用整除向下取整。
If the middle equals the target, return it.
如果中间元素等于目标，就返回它。
If the middle is smaller than the target, set low to mid plus one.
如果中间元素比目标小，就把下界设为中点加一。
Otherwise set high to mid minus one.
否则把上界设为中点减一。
Loop while low is still at most high.
只要下界还不超过上界就继续循环。
On the alphabet, finding W takes just three comparisons — M, then T, then W.
在字母表上找 W 只要三次比较——先是 M，再是 T，最后是 W。
Worst case is order log base two of n: for a million items, about twenty comparisons.
最坏情况是以二为底 n 的对数阶：一百万个元素大约二十次比较。
Sorting first costs order n log n once, then every later search is cheap.
先排序的一次性代价是 n 乘以 log n 阶，之后每一次查找都很便宜。
A bubble sort repeatedly walks the array, swapping any adjacent pair that is out of order, so the largest value bubbles to the end on each pass.
冒泡排序反复走过数组，交换任何顺序不对的相邻一对， 于是每一趟最大的值都会冒到末尾。
Next pass ignores that last cell and walks again.
下一趟忽略那个末尾格子，再走一遍。
A swapped flag tracks whether any swap happened; if a whole pass makes none, the list is already sorted and we can exit early.
一个交换标志记录本趟是否发生过交换；如果一整趟都没有交换， 列表已经有序，可以提前退出。
Best case is then order n — the list was already sorted.
最好情况于是是 n 阶——列表本来就有序。
Average and worst case are order n squared.
平均和最坏情况是 n 的平方阶。
Simple to write, but slow for large n.
写起来简单，但对大的 n 很慢。
An insertion sort builds a sorted prefix from the left.
插入排序从左边搭起一段有序的前缀。
It takes each new item as the key, then shifts every larger neighbour one place to the right until a hole opens, and drops the key in — exactly how people sort a hand of cards.
它把每一个新元素当作关键字， 再把每一个更大的邻居向右移一格，直到腾出一个空位，把关键字放进去—— 这正是人们整理一手扑克牌的方式。
Best case is order n when the list is already sorted; worst case is order n squared.
当列表已经有序时，最好情况是 n 阶； 最坏情况是 n 的平方阶。
It sorts in place, uses almost no extra memory, and is stable: it keeps the relative order of equal elements.
它是原地排序，几乎不用额外内存，而且是稳定的： 它保持相等元素的相对顺序。
That stability matters when you sort by one field and then another.
当你先按一个字段再按另一个字段排序时，稳定性很重要。
So how do we sort in the first place?
那么，我们一开始又是怎么排序的呢？
Two that you must know.
有两种你必须掌握。
A bubble sort walks the list comparing neighbours, and swaps any pair that is in the wrong order, so the biggest value bubbles to the end on every pass.
冒泡排序沿着列表走，比较相邻的两个元素， 把顺序不对的那一对交换过来，所以每一趟最大的值都会冒到末尾。
Repeat until a whole pass makes no swaps.
一直重复， 直到某一趟一次交换都没有发生为止。
An insertion sort builds a sorted section on the left: it takes each new item and slides it back past the larger ones until it drops into place — exactly how people sort a hand of cards.
插入排序则在左边慢慢搭起一段有序的区域： 它取出每一个新元素，让它往回滑过那些更大的元素，直到落进自己的位置—— 这正是人们整理一手扑克牌的方式。
Both are quadratic in the worst case, both sort in place with almost no extra memory, and insertion sort is the better one on a list that is already nearly sorted.
两者在最坏情况下都是平方级的， 也都是原地排序、几乎不用额外内存；而在一个本来就接近有序的列表上，插入排序更胜一筹。
A common exam task is to show the array after each outer pass.
一个常见的考试任务是写出每一趟外层循环之后的数组。
Take the letters D, T, H, R with insertion sort.
用插入排序处理字母 D、T、H、R。
Pass one takes key T: T is already bigger than D, so nothing changes.
第一趟取关键字 T：T 已经比 D 大，所以不变。
Pass two takes key H: H slides left past T, giving D, H, T, R.
第二趟取关键字 H： H 向左滑过 T，得到 D、H、T、R。
Pass three takes key R: R slides left past T and stops after H, giving D, H, R, T.
第三趟取关键字 R： R 向左滑过 T，停在 H 后面，得到 D、H、R、T。
Write each pass as a new row, shade the sorted prefix, and you earn the method marks even if a later value is wrong.
把每一趟写成新的一行，给有序前缀涂上阴影， 即便后面某个值写错了，你也能拿到方法分。
The abstract data types from earlier topics appear inside many algorithms.
前面专题里的抽象数据类型会出现在许多算法内部。
A stack drives depth-first traversal and undo: last in, first out.
栈驱动深度优先遍历和撤销： 后进先出。
A queue drives breadth-first traversal and print ordering: first in, first out.
队列驱动广度优先遍历和打印顺序：先进先出。
A linked list lets data grow and shrink without a fixed size.
链表让数据可以增长和缩小，而不需要固定大小。
You do not rebuild these from scratch every time — you use the ADT as a black box, and the algorithm that uses it need not know how it is built underneath.
你不必每次都从零重写它们——把抽象数据类型当作黑箱来用， 使用它的算法不必知道它底层是怎么实现的。
ADTs can be built from other ADTs, not just from arrays.
抽象数据类型可以由其他抽象数据类型构成，不只是由数组。
A queue can be made from two stacks.
队列可以用两个栈来实现。
A stack can be a linked list where push prepends a head node.
栈可以是一个链表，压栈就是在头部插入一个节点。
A queue can be a linked list with head and tail pointers.
队列可以是带有头指针和尾指针的链表。
A binary tree is nodes, each with up to two child pointers — left and right — and leaves that have none.
二叉树由节点组成， 每个节点最多有两个子指针——左和右——而叶子没有任何子节点。
A dictionary stores key-to-value pairs, often on a hash table.
字典存储键到值的配对，常常建立在哈希表上。
Layering this way separates concerns: the algorithm using the ADT stays simple, while the structure underneath can change.
这样分层可以分离关注点： 使用抽象数据类型的算法保持简单，而底层结构可以更换。
Walking a binary tree has three classic depth-first orders.
遍历一棵二叉树有三种经典的深度优先顺序。
Pre-order visits the root, then the left subtree, then the right.
前序遍历先访问根，再访问左子树，再访问右子树。
In-order visits left, then root, then right — and on a binary search tree that produces the values in sorted order.
中序遍历先左、再根、再右——在一棵二叉搜索树上，这会按有序顺序给出所有值。
Post-order visits left, then right, then the root.
后序遍历先左、再右、再根。
Recursion makes all three natural: each call handles one subtree, and the base case is an empty tree.
递归让这三种都显得自然： 每一次调用处理一棵子树，基本情形是一棵空树。
Look at this binary search tree with root four.
看这棵根为四的二叉搜索树。
Pre-order visits four, two, one, three, six, five, seven.
前序访问四、二、一、三、六、五、七。
In-order visits one, two, three, four, five, six, seven — sorted order, exactly.
中序访问一、二、三、四、五、六、七——恰好是有序顺序。
Post-order visits one, three, two, five, seven, six, four.
后序访问一、三、二、五、七、六、四。
Exam questions often give the tree and ask for one of these sequences, or give a sequence and ask which order was used.
考题常常给出树并要求写出其中一种序列， 或者给出序列并问用的是哪种顺序。
In-order of a binary search tree is the reliable way to list its keys in ascending order.
对二叉搜索树做中序遍历， 是按升序列出其关键字的可靠办法。
Now, how do we compare algorithms fairly?
那么，我们又该怎样公平地比较算法呢？
Not in seconds — a fast computer would flatter a bad algorithm.
不是用秒——一台快的电脑会把一个糟糕的算法衬托得很好看。
Instead we use Big-O notation, which describes how the running time grows as the input grows.
我们用的是大O表示法，它描述的是运行时间如何随着输入的增大而增长。
Constant time does not care how big the input is.
常数时间根本不在乎输入有多大。
Logarithmic growth is binary search.
对数级增长就是二分查找。
Linear growth is one pass over the data.
线性增长就是把数据整个过一遍。
The good sorts are only a little worse than linear.
好的排序算法只比线性差一点点。
And bubble and insertion sort are quadratic: double the input, and the work goes up four times.
而冒泡排序和插入排序是平方级的：输入翻一倍，工作量就变成四倍。
Watch the curves — at scale, the order of growth decides the winner, not raw speed.
看这些曲线——到了大规模的时候，决定胜负的是增长的量级，而不是原始速度。
Time complexity is how running time grows with input size n, written as the dominant term in Big-O.
时间复杂度描述运行时间如何随输入规模 n 增长，写成大O中的主导项。
Order one is constant.
一阶是常数。
Order log n is binary search.
log n 阶是二分查找。
Order n is linear search.
n 阶是线性查找。
Order n log n is a good sort such as merge sort or quick sort.
n 乘以 log n 阶是好的排序，比如归并排序或快速排序。
Order n squared is bubble and insertion sort.
n 的平方阶是冒泡排序和插入排序。
A smaller order wins at scale, even if another algorithm is faster for small n.
在大规模时，更小的阶会赢， 即便另一个算法在小的 n 上更快。
To sort a million items, an order n log n sort finishes in a fraction of a second, while an order n squared sort can take minutes.
要给一百万个元素排序， n 乘以 log n 阶的排序只要零点几秒，而 n 的平方阶排序可能要几分钟。
This graph makes the gap real.
这张图让差距变得真实。
Bubble sort and insertion sort climb steeply as order n squared.
冒泡排序和插入排序作为 n 的平方阶陡然上升。
A quick sort stays low as order n log n.
快速排序作为 n 乘以 log n 阶保持很低。
For a few dozen elements the difference is tiny; once n reaches thousands or millions, the quadratic curve pulls far away.
对于几十个元素，差别微不足道； 一旦 n 到了几千或几百万，平方曲线就远远甩开。
That is why exam answers name the order, not a stopwatch time — and why you reach for a better sort once the data stops being small.
这就是为什么考题答案要写增长的量级，而不是秒表时间—— 也是为什么数据一旦不再小，你就要改用更好的排序。
A sorted list holds one thousand items.
一个有序列表有一千个元素。
How many comparisons does each search need in the worst case?
两种查找在最坏情况下各需要多少次比较？
A linear search checks items one at a time, so it may need up to one thousand comparisons — that is order n.
线性查找一次检查一个，所以最多可能需要一千次比较——这是 n 阶。
A binary search halves the list each step, so it needs at most the ceiling of log base two of one thousand, which is ten comparisons — that is order log n.
二分查找每一步把列表对半分，所以最多需要以二为底一千的对数向上取整， 也就是十次比较——这是 log n 阶。
Doubling the list to two thousand items adds only one comparison to the binary search, but up to another one thousand to the linear search.
把列表翻倍到两千个元素， 二分查找只多加一次比较，而线性查找最多再多一千次。
That is why the order of growth, not raw speed, decides the winner at scale.
这就是为什么在大规模时，决定胜负的是增长的量级，而不是原始速度。
Space complexity is the extra memory needed beyond the input itself.
空间复杂度是除输入本身以外还需要的额外内存。
Bubble and insertion sort use order one extra — they sort in place.
冒泡排序和插入排序只用一阶额外空间—— 它们是原地排序。
Merge sort uses order n extra for the temporary arrays.
归并排序为临时数组使用 n 阶额外空间。
Recursion uses stack memory proportional to its depth.
递归使用与深度成正比的栈内存。
There is often a time-memory trade-off: spend more memory to go faster, or accept slower work to stay lean.
往往存在时间与内存的权衡： 多花内存换更快，或者接受更慢以保持精简。
Other criteria matter too.
其他标准也很重要。
Simplicity means easier to code and maintain.
简单性意味着更容易编写和维护。
Stability keeps equal elements in their original order.
稳定性保持相等元素的原始顺序。
Adaptiveness means faster on nearly-sorted data.
自适应性意味着在接近有序的数据上更快。
The right algorithm depends on the data and the constraints.
正确的算法取决于数据和约束。
Last, recursion — a routine that calls itself on a smaller version of the same problem.
最后是递归——一个在同一问题的更小版本上调用自己的例程。
It needs two parts: a base case, small enough to answer directly, which stops the chain; and a recursive case, which shrinks the input and calls itself.
它需要两个部分： 一个基本情形，小到可以直接给出答案，用来终止这条链；以及一个递归情形， 它缩小输入并调用自己。
Take factorial of four.
以四的阶乘为例。
It calls factorial of three, which calls factorial of two, which calls factorial of one — and that is the base case, which simply returns one.
它调用三的阶乘，三的阶乘再调用二的阶乘， 二的阶乘又调用一的阶乘——而那就是基本情形，直接返回一。
Now the chain unwinds: two, then six, then twenty-four.
现在这条链开始回退： 二，然后六，然后二十四。
Every call gets its own stack frame, holding its parameters, its local variables and the return address, so the calls never trample each other.
每一次调用都有自己的栈帧，里面装着它的参数、 它的局部变量和返回地址，所以各次调用之间从不会互相踩踏。
And that is also the danger: forget the base case, and the stack keeps growing until it overflows.
而这也正是危险所在：忘了基本情形，栈就会一直长下去，直到溢出。
Watch the call stack wind up and unwind.
看调用栈怎样向上卷起再向下回退。
Each recursive call pushes a new frame.
每一次递归调用都压入一个新栈帧。
Factorial of four cannot answer yet, so it calls three; three calls two; two calls one — the base case — which answers one straight back.
四的阶乘还答不上来，于是调用三；三调用二；二调用一——基本情形—— 直接返回一。
Then the answers multiply outward: two times one is two, three times two is six, four times six is twenty-four.
然后答案向外相乘：二乘一是二，三乘二是六，四乘六是二十四。
Recursion is natural for self-similar problems: trees, divide-and-conquer such as binary search and merge sort, and nested data.
递归对自相似问题很自然：树、分治（比如二分查找和归并排序），以及嵌套数据。
When it is a poor fit, a plain loop is usually cleaner.
当它不合适时，一个普通循环通常更干净。
What does the compiler do for recursive code?
编译器为递归代码做了什么？
Each call needs its own copy of its parameters and local variables.
每一次调用都需要自己那一份参数和局部变量。
The compiler keeps these on the call stack.
编译器把它们放在调用栈上。
For each call it pushes a stack frame holding the parameters, the local variables, and the return address — where to resume in the caller.
对每一次调用，它压入一个栈帧， 里面装着参数、局部变量和返回地址——也就是调用者里从哪里继续。
When the function returns, the return value is handed back, the frame is popped, and control resumes at that address.
当函数返回时，返回值被交回，栈帧被弹出，控制在那个地址恢复。
There is no special recursion mechanism: this is the same call-and-return path used for ordinary non-recursive calls.
没有特殊的「递归机制」：这与普通非递归调用用的是同一条调用与返回路径。
Deep recursion simply makes the stack grow large, which is why it may overflow.
很深的递归只是让栈长得很大，所以可能溢出。
Three risks to name in an exam answer.
考题答案里要能点出三种风险。
First, infinite recursion if the base case is missed — the program crashes with a stack overflow.
第一，如果漏了基本情形就会无限递归—— 程序以栈溢出崩溃。
Second, high memory use for deep recursion, because every frame stays on the stack until it returns.
第二，很深的递归内存占用很高， 因为每一个栈帧在返回前都留在栈上。
Third, it can be slow if it repeats work: a naive Fibonacci recomputes the same values again and again, and that is exponential.
第三，如果重复计算就会很慢： 朴素的斐波那契会一遍又一遍地重算相同的值，那是指数级的。
Fix it with a loop, or with memoisation that stores answers already computed.
用循环来修，或者用记忆化把已经算过的答案存起来。
Recursion is powerful, but it is not free.
递归很强大，但不是免费的。
Three marks to lock in.
三个要拿稳的分。
First, match each algorithm to its Big-O: linear search is linear, binary search is logarithmic, bubble and insertion sort are quadratic.
第一，把每种算法和它的大O对上号：线性查找是线性的，二分查找是对数的， 冒泡排序和插入排序是平方的。
Second, always say that binary search needs a sorted list — that one condition is worth marks on its own.
第二，一定要写出二分查找需要一个有序的列表—— 光这一个条件本身就能得分。
Third, a recursive routine needs a base case and a call to itself, and deep recursion overflows the call stack.
第三，递归例程需要一个基本情形和一次对自己的调用， 而过深的递归会让调用栈溢出。
Nail these, and this topic is yours.
掌握这些，这个专题就是你的了。
Three more habits.
再三个习惯。
Trace a sort or search with a table when asked, showing each pass or each low-mid-high step — partial credit lives in the working.
被要求时，用表格追踪排序或查找，写出每一趟或每一步的下界、中点、上界—— 部分分就在过程里。
Name that good sorts are order n log n, not only the slow quadratic ones.
要写出好的排序是 n 乘以 log n 阶，不只是慢的平方阶那些。
And when a question asks about memory, name the space cost: in-place sorts use constant extra space; merge sort and deep recursion use more.
当题目问到内存时，写出空间代价：原地排序用常数额外空间； 归并排序和很深的递归用得更多。
Write the order in words if you like — order n, order log n, order n squared — the marks care about the idea.
你可以用文字写量级—— n 阶、log n 阶、n 的平方阶——分数看的是这个概念。