1
00:00:06,641 --> 00:00:08,997
你是大學圖書館的管理員。

2
00:00:08,997 --> 00:00:11,397
正在享受午後的閒暇時光。

3
00:00:11,397 --> 00:00:17,771
這時候，突然送來了1280 本書！

4
00:00:17,771 --> 00:00:21,520
這些書被排成一行，

5
00:00:21,520 --> 00:00:23,378
但是毫無規律。

6
00:00:23,378 --> 00:00:26,761
剛好，自動分類系統又發生故障。

7
00:00:26,761 --> 00:00:29,667
更糟糕的是，明天就要開學了；

8
00:00:29,667 --> 00:00:32,005
也就是說明天一大早，

9
00:00:32,005 --> 00:00:36,307
學生們就會湧入圖書館借書。

10
00:00:36,307 --> 00:00:39,263
如何才能把所有書籍
及時整理好？

11
00:00:39,263 --> 00:00:44,509
第一種方法：你可以從
排在最前面的兩本書開始，

12
00:00:44,509 --> 00:00:48,526
如果這兩本書的順序正確，
那麼不做任何變動；

13
00:00:48,526 --> 00:00:50,920
否則，互相交換這兩本書的位置。

14
00:00:50,920 --> 00:00:53,216
接著再看第二本書和第三本書，

15
00:00:53,216 --> 00:00:54,879
不斷重複上述過程，

16
00:00:54,879 --> 00:00:57,935
一直到書列的末端為止。

17
00:00:57,935 --> 00:01:01,185
在過程中，你可能就會碰到
應該排在最後的那一本書，

18
00:01:01,185 --> 00:01:04,710
你會持續將這本書和後面的書交換，

19
00:01:04,710 --> 00:01:09,030
將它不斷往後移動，
一直到最後面的位置。

20
00:01:09,030 --> 00:01:11,075
然後再從頭開始，

21
00:01:11,075 --> 00:01:15,260
不斷重複上述的步驟，
將倒數第二本書歸位，

22
00:01:15,260 --> 00:01:18,521
一直持續到所有的書
都放在正確的位置為止。

23
00:01:18,521 --> 00:01:21,862
這種整理的方法
叫做「氣泡排序法」。

24
00:01:21,862 --> 00:01:24,156
原理很簡單，但過程很緩慢。

25
00:01:24,156 --> 00:01:29,251
在第一輪過程就需要進行
1279 次的比較；

26
00:01:29,251 --> 00:01:33,623
第二輪要比較 1278 次，
以此類推……

27
00:01:33,623 --> 00:01:38,542
所以總共要比較 818,560 次。

28
00:01:38,542 --> 00:01:40,833
如果比較一次需要 1 秒，


29
00:01:40,833 --> 00:01:44,003
那麼你需要花費 9.5 天才能完成工作。

30
00:01:44,003 --> 00:01:48,569
第二種方法是先將前面兩本書排好，

31
00:01:48,569 --> 00:01:53,523
然後將第三本書
與位於第二位的書進行比較。

32
00:01:53,523 --> 00:01:57,173
如果第三本書應該放在第二本之前，
則互相交換它們的位置，

33
00:01:57,173 --> 00:01:59,641
然後再將這本書
與排在第一位的書比較，

34
00:01:59,641 --> 00:02:01,682
如果有需要，就再交換位置。

35
00:02:01,682 --> 00:02:03,880
現在，你已經成功安排好了前三本書，

36
00:02:03,880 --> 00:02:07,732
接著每次將一本書
加入之前安排好的隊列中，

37
00:02:07,732 --> 00:02:11,809
將新書與前一本作比較，
如果需要，交換它們的位置，

38
00:02:11,809 --> 00:02:15,784
一直到這本新書被安置到
隊列中的正確位置。

39
00:02:15,784 --> 00:02:17,944
這種方法叫做「插入排序法」。

40
00:02:17,944 --> 00:02:19,534
與氣泡排序法不同，

41
00:02:19,534 --> 00:02:23,194
它通常不需要比較
所有相鄰的兩本書。

42
00:02:23,194 --> 00:02:26,764
平均來說，每本書
需要進行比較的次數

43
00:02:26,764 --> 00:02:29,274
僅有氣泡排序法的一半。

44
00:02:29,274 --> 00:02:35,533
這種方法總共需要比較
409,280 次，

45
00:02:35,533 --> 00:02:37,895
大約需要 5 天時間。

46
00:02:37,895 --> 00:02:40,624
然而，你需要比較的次數還是太多。

47
00:02:40,624 --> 00:02:42,515
更好的辦法是，

48
00:02:42,515 --> 00:02:46,475
首先，隨機選取一本書，
我們稱之為「分割點」；

49
00:02:46,475 --> 00:02:49,606
將其他的每一本書
與分割點作比較，

50
00:02:49,606 --> 00:02:51,495
然後根據分割點，
將這一排書分成兩部分，

51
00:02:51,495 --> 00:02:55,296
將所有應該在分割點
之前的書放在左邊，

52
00:02:55,296 --> 00:02:58,715
在分割點之後的書放在右邊，

53
00:02:58,715 --> 00:03:00,415
這樣你就節省了大把時間，

54
00:03:00,415 --> 00:03:03,845
因為不用再將分割點左半邊的書

55
00:03:03,845 --> 00:03:07,095
與右邊的書進行比較。

56
00:03:07,095 --> 00:03:09,665
現在，我們只關注分割點左邊的書，

57
00:03:09,665 --> 00:03:12,542
你可以再一次隨機選一本書
作為新的分割點，

58
00:03:12,542 --> 00:03:17,016
然後將其他的書分配在
新的分割點左右兩邊。

59
00:03:17,016 --> 00:03:19,736
你可以繼續建立這種「子分割點，」

60
00:03:19,736 --> 00:03:22,384
一直到分出了許多小型分支，

61
00:03:22,384 --> 00:03:25,794
每一個分支中，
可以用其他更快的排序法，

62
00:03:25,794 --> 00:03:27,524
例如插入排序法。

63
00:03:27,524 --> 00:03:33,236
每一輪分割大約需要
進行 1280 次比較，

64
00:03:33,236 --> 00:03:35,736
如果你的分割點分佈的非常均勻，

65
00:03:35,736 --> 00:03:39,576
整排書分為 128 個分支，
每個分支 10 本書，

66
00:03:39,576 --> 00:03:43,947
這樣大約需要七輪分割，
也就是 8960 秒。

67
00:03:43,947 --> 00:03:48,586
每個分支當中，
大約需要再花 22 秒進行排序。

68
00:03:48,586 --> 00:03:49,346
總體上來說，

69
00:03:49,346 --> 00:03:51,817
這種稱為「快速排序法」的方法，

70
00:03:51,817 --> 00:03:54,713
能將所有的書
在三個半小時內排列整齊。

71
00:03:54,713 --> 00:03:55,717
但是這有個陷阱。

72
00:03:55,717 --> 00:03:57,757
如果你的分割點非常偏向某一端，

73
00:03:57,757 --> 00:03:59,575
就無法節省時間。

74
00:03:59,575 --> 00:04:01,477
幸運的是，這種情況幾乎不會發生。

75
00:04:01,477 --> 00:04:02,930
這就是為什麼快速分類法

76
00:04:02,930 --> 00:04:06,916
在程式設計中
是最有效率的排序法之一。

77
00:04:06,916 --> 00:04:10,847
例如在購物網站上，
將商品依照價格排序；

78
00:04:10,847 --> 00:04:14,728
或是列出某個地點附近的加油站，

79
00:04:14,728 --> 00:04:16,379
然後根據距離來排序。

80
00:04:16,379 --> 00:04:20,407
在這個排書的例子中，
快速排序法幫你節省了許多時間。

81
00:04:20,407 --> 00:04:22,778
真是多麼驚險刺激的一天啊！