You work at the college library.
你在大学图书馆工作
You're in the middle of a quiet afternoon when suddenly a shipment of 1,280 different books arrives.
你正在享受在一个静谧的午后这时运过来1280本不同的书
The books have been dropped of in one long straight line, but they're all out of order,
书被卸下来摆成长长一排而且顺序是混乱的
and the automatic sorting system is broken.
这时自动排序系统也坏了
To make matters worse, classes start tomorrow,
更糟糕的是 明天就开学了
which means that first thing in the morning, students will show up in droves looking for these books.
这就意味着明天一大早学生们将争相来搜寻他们所需要的书
How can you get them all sorted in time?
你如何及时把它们整理好呢
One way would be to start at one end of the line with the first pair of books.
一种方法是从排在书列端点的两本书开始
If the first two books are in order, then leave them as they are.
如果这两本书已经按顺序排好了 那就不要再动它们了
Otherwise, swap them.
否则 就把它们调换一下
Then, look at the second and third books, repeat the process,
之后 看看第二本 第三本如此进行下去
and continue until you reach the end of the line.
直至你摆到最后一本书
At some point, you'll come across the book that should be last,
有时候 你可能会遇到应该排在最后的那本书
and keep swapping it with every subsequent book,
这就需要把它和随后的每一本书调换位置
moving it down the line until it reaches the end where it belongs.
不停地向后调换 直至调到最后它该呆的地方
Then, start from the beginning and repeat the process to get the second to last book in its proper place,
然后从头开始 重复这一过程把第二本和剩下的书都依次合适地摆放
and keep going until all books are sorted.
继续下去直到所有的书都被放到正确的位置
This approach is called Bubble Sort.
这种方法被称为上推分类法
It's simple but slow.
它很简单但是很耗时
You'd make 1,279 comparisons in the first round,then 1,278, and so on, adding up to 818,560 comparisons.
第一轮下来你一共要进行1279次对比然后是1278次 这样依次下去完成整个过程一共要进行818560次对比

If each took just one second, the process would take over nine days.
如果每次比较花一秒 完成整个过程需要超过9天的时间
A second strategy would be to start by sorting just the first two books.
第二种方法是从前两本开始排序
Then, take the third book and compare it with the book in the second spot.
之后 把第三本和第二本进行对比
If it belongs before the second book, swap them,
如果它应该排第二本前面 那就把它们调换一下
then compare it with the book in the first spot, and swap again if needed.
然后再把它和第一本对比如果它应排第一 那就再调换一次
Now you've sorted the first three books.
那么现在前三本书就排好了
Keep adding one book at a time to the sorted sub-line,
每次在排好的书列里加一本书
comparing and swapping the new book with the one before it
将这本新加入的书与其前一个对比 调换
until it's correctly placed among the books sorted so far.
直到它被正确地放到已经排好的书列中
This is called Insertion Sort.
这种方法被称为插入式分类法
Unlike Bubble Sort, it usually doesn't require comparing every pair of books.
不像上推分类法 这种方法不需要把所有的书两两对比
On average, we'd expect to only need to compare each book to half of the books that came before it.
平均来说 我们估计只需要将每本书与排在前面的一半的书进行对比
In that case, the total number of comparisons would be 409,280, taking almost five days.
那样对比的总次数就是409,280,花费大约五天的时间
You're still doing way too many comparisons.
你仍然需要很多次的对比
Here's a better idea.
这有一个更好的办法
First, pick a random book.
首先 随机抽取一本书
Call it the partition and compare it to every other book.
把它作为分隔参照物与其他的书相对比
Then, divide the line by placing all the books that come before the partition on its left
然后将所有排在其前面的书放在它的左边
and all the ones that come after it on its right.
把应该排在它右边的书放在它的右边
You've just saved loads of time by not having to compare any of the books on the left to any of the ones on the right ever again.
这样你就能节省很多时间 因为左边的书不用再跟其右边的书再进行一一对比了
Now, looking only at the books on the left, you can again pick a random partition book
现在只看左边的书 然后你从里面再拿出一本书作为分割参照物
and separate those books that come before it from those that come after it.
然后将排在它后面的排在它前面的书分开
You can keep creating sub-partitions like this until you have a bunch of small sub-lines,
你可以一直这样创造作为分割线的书直到这排书变成了一群分开的更小排的书
each of which you'd sort quickly using another strategy, like Insertion Sort.
这时你就可以将每个小段的书用其他方法排好了 比如 插入排序法
Each round of partitioning requires about 1,280 comparisons.
每次划分需要1280次的对比
If your partitions are pretty balanced,
如果你设置的参照物位置很平均的话
dividing the books into 128 sub-lines of ten would take about seven rounds,or 8,960 seconds.
把这些书以10本为一段 一共分128段 大概需要7轮能分好也就是8960秒
Sorting these sub-lines would add about 22 seconds each.
每一小段的排序大概要花22秒钟
All in all, this method known as QuickSort could sort the books in under three and a half hours.
总而言之 这种方法被叫做快速分类法排好这些书不超过三个半小时
But there's a catch.
但有一个问题
Your partitions could end up lopsided, saving no time at all.
如果选取的参照物非常不对称 则根本无法节约时间
Luckily, this rarely happens.
幸运的是 这种情况很少发生
That's why QuickSort is one of the most efficient strategies used by programmers today.
这就是为何快速分类法是如今程序员使用的最高效的方法之一
They use it for things like sorting items in an online store by price,
他们用这种方法将网店里需要以价格分类的商品进行归类
or creating a list of all the gas stations close to a given location sorted by distance.
将某个位置附近的加油站以距离远近的顺序列一个表
In your case, you're done quick sorting with time to spare.
至于你 你已经快速分好类而且还有剩余时间
Just another high-stakes day in the library.
在图书馆等待另一个高强度的一天吧