What's the fastest way to alphabetize your bookshelf? - Chand John

翻译人员: Kai Ma 校对人员: Mingyu Cui

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,

在第一次循环中， 你需要进行1279次对比，

then 1,278, and so on,

第二次循环则需要1278次，

adding up to 818,560 comparisons.

总计818560次对比。

If each took just one second, the process would take over nine days.

按每次比较需要1秒， 这一过程将长达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,

也就是409280次。

taking almost five days.

需要将近5天的时间。

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,

那么把整列书分成128个分支，每个10本， 大约只需要7次循环，

or 8,960 seconds.

也就是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.

多么充满乐趣的一天。