如何最有效率地整理書架？- Chand John
-
0:07 - 0:09你是大學圖書館的管理員。
-
0:09 - 0:11正在享受午後的閒暇時光。
-
0:11 - 0:18這時候，突然送來了1280 本書！
-
0:18 - 0:22這些書被排成一行，
-
0:22 - 0:23但是毫無規律。
-
0:23 - 0:27剛好，自動分類系統又發生故障。
-
0:27 - 0:30更糟糕的是，明天就要開學了；
-
0:30 - 0:32也就是說明天一大早，
-
0:32 - 0:36學生們就會湧入圖書館借書。
-
0:36 - 0:39如何才能把所有書籍
及時整理好？ -
0:39 - 0:45第一種方法：你可以從
排在最前面的兩本書開始， -
0:45 - 0:49如果這兩本書的順序正確，
那麼不做任何變動； -
0:49 - 0:51否則，互相交換這兩本書的位置。
-
0:51 - 0:53接著再看第二本書和第三本書，
-
0:53 - 0:55不斷重複上述過程，
-
0:55 - 0:58一直到書列的末端為止。
-
0:58 - 1:01在過程中，你可能就會碰到
應該排在最後的那一本書， -
1:01 - 1:05你會持續將這本書和後面的書交換，
-
1:05 - 1:09將它不斷往後移動，
一直到最後面的位置。 -
1:09 - 1:11然後再從頭開始，
-
1:11 - 1:15不斷重複上述的步驟，
將倒數第二本書歸位， -
1:15 - 1:19一直持續到所有的書
都放在正確的位置為止。 -
1:19 - 1:22這種整理的方法
叫做「氣泡排序法」。 -
1:22 - 1:24原理很簡單，但過程很緩慢。
-
1:24 - 1:29在第一輪過程就需要進行
1279 次的比較； -
1:29 - 1:34第二輪要比較 1278 次，
以此類推…… -
1:34 - 1:39所以總共要比較 818,560 次。
-
1:39 - 1:41如果比較一次需要 1 秒，
-
1:41 - 1:44那麼你需要花費 9.5 天才能完成工作。
-
1:44 - 1:49第二種方法是先將前面兩本書排好，
-
1:49 - 1:54然後將第三本書
與位於第二位的書進行比較。 -
1:54 - 1:57如果第三本書應該放在第二本之前，
則互相交換它們的位置， -
1:57 - 2:00然後再將這本書
與排在第一位的書比較， -
2:00 - 2:02如果有需要，就再交換位置。
-
2:02 - 2:04現在，你已經成功安排好了前三本書，
-
2:04 - 2:08接著每次將一本書
加入之前安排好的隊列中， -
2:08 - 2:12將新書與前一本作比較，
如果需要，交換它們的位置， -
2:12 - 2:16一直到這本新書被安置到
隊列中的正確位置。 -
2:16 - 2:18這種方法叫做「插入排序法」。
-
2:18 - 2:20與氣泡排序法不同，
-
2:20 - 2:23它通常不需要比較
所有相鄰的兩本書。 -
2:23 - 2:27平均來說，每本書
需要進行比較的次數 -
2:27 - 2:29僅有氣泡排序法的一半。
-
2:29 - 2:36這種方法總共需要比較
409,280 次， -
2:36 - 2:38大約需要 5 天時間。
-
2:38 - 2:41然而，你需要比較的次數還是太多。
-
2:41 - 2:43更好的辦法是，
-
2:43 - 2:46首先，隨機選取一本書，
我們稱之為「分割點」； -
2:46 - 2:50將其他的每一本書
與分割點作比較， -
2:50 - 2:51然後根據分割點，
將這一排書分成兩部分， -
2:51 - 2:55將所有應該在分割點
之前的書放在左邊， -
2:55 - 2:59在分割點之後的書放在右邊，
-
2:59 - 3:00這樣你就節省了大把時間，
-
3:00 - 3:04因為不用再將分割點左半邊的書
-
3:04 - 3:07與右邊的書進行比較。
-
3:07 - 3:10現在，我們只關注分割點左邊的書，
-
3:10 - 3:13你可以再一次隨機選一本書
作為新的分割點， -
3:13 - 3:17然後將其他的書分配在
新的分割點左右兩邊。 -
3:17 - 3:20你可以繼續建立這種「子分割點，」
-
3:20 - 3:22一直到分出了許多小型分支，
-
3:22 - 3:26每一個分支中，
可以用其他更快的排序法， -
3:26 - 3:28例如插入排序法。
-
3:28 - 3:33每一輪分割大約需要
進行 1280 次比較， -
3:33 - 3:36如果你的分割點分佈的非常均勻，
-
3:36 - 3:40整排書分為 128 個分支，
每個分支 10 本書， -
3:40 - 3:44這樣大約需要七輪分割，
也就是 8960 秒。 -
3:44 - 3:49每個分支當中，
大約需要再花 22 秒進行排序。 -
3:49 - 3:49總體上來說，
-
3:49 - 3:52這種稱為「快速排序法」的方法，
-
3:52 - 3:55能將所有的書
在三個半小時內排列整齊。 -
3:55 - 3:56但是這有個陷阱。
-
3:56 - 3:58如果你的分割點非常偏向某一端，
-
3:58 - 4:00就無法節省時間。
-
4:00 - 4:01幸運的是，這種情況幾乎不會發生。
-
4:01 - 4:03這就是為什麼快速分類法
-
4:03 - 4:07在程式設計中
是最有效率的排序法之一。 -
4:07 - 4:11例如在購物網站上，
將商品依照價格排序； -
4:11 - 4:15或是列出某個地點附近的加油站，
-
4:15 - 4:16然後根據距離來排序。
-
4:16 - 4:20在這個排書的例子中，
快速排序法幫你節省了許多時間。 -
4:20 - 4:23真是多麼驚險刺激的一天啊！
- Title:
- 如何最有效率地整理書架？- Chand John
- Speaker:
- Chand John
- Description:
-
more » « less
觀看完整課程： http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john
想像你在一座大學圖書館裡工作。你正在享受下午的閒暇時光，這時突然送來了1280 本書。這些書毫無規律地排成一行，而自動排序系統又發生了故障。那麼，如何才能在最短的時間內排列好所有的書籍？Chand John 向我們闡述如何利用演算法，來幫助圖書管理員和搜索引擎快速地排序資料。
課程製作： Chand John，動畫製作 Anton Trofimov
- Video Language:
- English
- Team:
closed TED
- Project:
- TED-Ed
- Duration:
- 04:39
|
Regina Chu edited Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? | |
|
TED Translators admin approved Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? | |
|
庭芝 梁 accepted Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? | |
|
|
庭芝 梁 edited Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? | |
|
|
庭芝 梁 edited Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? | |
|
|
庭芝 梁 edited Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? | |
|
|
庭芝 梁 edited Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? | |
|
|
庭芝 梁 edited Chinese, Traditional subtitles for What's the fastest way to alphabetize your bookshelf? |