ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

五分钟教你快速整理书架 – 译学馆
未登陆,请登陆后再发表信息
最新评论 (0)
播放视频

五分钟教你快速整理书架

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

你在大学图书馆上班
You work at the college library.
在一个静谧的午后
You’re in the middle of a quiet afternoon
1280本不同的书被车子运过来了
when suddenly a shipment of 1,280 different books arrives.
书被卸下来并被摆成一条长长的直线
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.
第一轮下来你一共要进行1279次对比
You’d make 1,279 comparisons in the first round,
然后是1278次 这样依次下去
then 1,278, and so on,
完成整个过程一共要进行818560次对比
adding up to 818,560 comparisons.
如果每次比较花一秒 完成整个过程需要超过9天的时间
If each took just one second, the process would take over nine days.
第二种方法是从前两本开始排序
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
会是409280次
would be 409,280,
要花差不多五天时间
taking almost five days.
这样的工作量还是太大了
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.
每一轮大概需要进行1280次对比
Each round of partitioning requires about 1,280 comparisons.
如果你设置的参照物位置很平均的话
If your partitions are pretty balanced,
把这些书以10本为一段 一共分128段 大概需要7轮能分好
dividing the books into 128 sub-lines of ten would take about seven rounds,
也就是8960秒
or 8,960 seconds.
每一小段的排序大概要花22秒钟
Sorting these sub-lines would add about 22 seconds each.
总而言之 这种方法被叫做快速分类法
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.

发表评论

译制信息
视频概述
听录译者

收集自网络

翻译译者

启点—飞雪群山

审核员

自动通过审核

视频来源

https://www.youtube.com/watch?v=WaNLJf8xzC4

相关推荐