1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [歸併排序]

2
00:00:02,000 --> 00:00:04,000
[羅布·鮑登 - 哈佛大學]

3
00:00:04,000 --> 00:00:07,000
[這是CS50。 -  CS50.TV]

4
00:00:07,000 --> 00:00:09,000
讓我們來談談有關合併排序。

5
00:00:09,000 --> 00:00:14,000
到目前為止，您已經看到冒泡排序，插入排序，選擇排序。

6
00:00:14,000 --> 00:00:17,000
雖然我種我的手，我的意思更好地波，

7
00:00:17,000 --> 00:00:21,000
合併排序通常執行比這3類。

8
00:00:22,000 --> 00:00:27,000
>> 但在談論合併排序之前，讓我們來談談關於合併的2個排序的列表。

9
00:00:27,000 --> 00:00:31,000
我們會給你打電話的過程中，2排序的列表，像這樣的，

10
00:00:31,000 --> 00:00:35,000
使一個單一的排序列表中的他們 - 合併列表。

11
00:00:35,000 --> 00:00:37,750
如何才能做到這一點呢？

12
00:00:37,750 --> 00:00:41,290
好了，一個想法，就是堅持一個列表到其他列表

13
00:00:41,290 --> 00:00:43,830
，然後在結果列表進行排序。

14
00:00:43,830 --> 00:00:47,220
>> 雖然這個工作，這是一個許多不必要的工作。

15
00:00:47,220 --> 00:00:49,900
我們可以做得更快比剛排序。

16
00:00:49,900 --> 00:00:54,100
請注意，一個錯誤的觀念，是採取交替杯，從每個列表中。

17
00:00:54,100 --> 00:00:56,460
雖然這可能看起來像這樣的作品，在第一，

18
00:00:56,460 --> 00:01:05,760
這樣做，我們最終4，8，15，23，16  - 通知，16日和23出來的地方。

19
00:01:05,760 --> 00:01:09,380
這是因為，在合併後的名單應該會出現連續的2個元素

20
00:01:09,380 --> 00:01:11,720
是在相同的初始列表。

21
00:01:11,720 --> 00:01:14,850
15和16都在左側列表中的。

22
00:01:14,850 --> 00:01:19,810
關鍵是要充分利用已排序的事實，這兩個列表。

23
00:01:19,810 --> 00:01:23,320
這意味著，如果我們只是看在兩個列表中的第一個元素 - 

24
00:01:23,320 --> 00:01:29,580
在這裡，4和8  - 其中之一也必須合併後的列表中的第一個元素。

25
00:01:29,580 --> 00:01:31,620
好了，這是為什麼？

26
00:01:31,620 --> 00:01:33,520
這兩個列表都已經排序，

27
00:01:33,520 --> 00:01:38,410
等4個或8時，必須是最小的元素，我們結合2列出了。

28
00:01:38,410 --> 00:01:41,770
在這種情況下，最小的是4，

29
00:01:41,770 --> 00:01:46,370
因此，我們可以拿出4，我們的合併列表中的第一個元素。

30
00:01:46,370 --> 00:01:50,710
現在我們將繼續合併剩餘的3個元素​​的第一個列表

31
00:01:50,710 --> 00:01:52,920
和4個元素的第二列表。

32
00:01:52,920 --> 00:01:57,150
>> 再次，我們只需要看看這兩個列表中的第一個元素。

33
00:01:57,150 --> 00:02:01,060
中的較小者的2必須是我們的合併列表中的第二個元素。

34
00:02:01,060 --> 00:02:05,440
這一次，8和15之間，最小的是8，所以我們插入，

35
00:02:05,440 --> 00:02:09,240
作為我們的排序的列表的第二個元素。

36
00:02:09,240 --> 00:02:12,180
我們可以繼續比較這兩個列表中的第一個元素

37
00:02:12,180 --> 00:02:14,420
並除去2的小的。

38
00:02:14,420 --> 00:02:19,460
15日和23日，15相比較小，所以這是我們的第三個元素。

39
00:02:21,000 --> 00:02:23,910
現在比較16和23中，圖16是較小的。

40
00:02:23,910 --> 00:02:26,820
所以這是第四個元素。

41
00:02:26,820 --> 00:02:30,390
>> 請注意，2個元素是從同一個列表中的行。

42
00:02:30,390 --> 00:02:34,400
這是為什麼合併後的清單不能只是備用2個列表元素。

43
00:02:34,400 --> 00:02:40,020
比較50和23，23小，所以我們選擇。

44
00:02:40,770 --> 00:02:44,070
在50和42之間，42是較小的。

45
00:02:44,070 --> 00:02:48,290
在50和108之間，50是較小的。

46
00:02:48,290 --> 00:02:52,330
最後，我們只是有108個，所以一定要在我們的名單。

47
00:02:53,750 --> 00:02:56,180
請注意，我們有一個很好的，排序的列表。

48
00:02:56,180 --> 00:02:59,040
每次我們比較了2列出了前2個元素

49
00:02:59,040 --> 00:03:02,730
我們能夠確定合併後的列表中的下一個元素。

50
00:03:02,730 --> 00:03:08,070
這意味著，如果最終的列表包含n個號碼，其中，n是8，

51
00:03:08,070 --> 00:03:12,610
然後，我們需要在最n次比較這些數字放到合適的地方。

52
00:03:13,230 --> 00:03:16,230
這樣的算法的所述以線性時間運行，

53
00:03:16,230 --> 00:03:18,090
不過不用擔心，在這裡。

54
00:03:18,570 --> 00:03:22,810
>> 使用我們的算法進行合併，我們就可以進行快速的合併排序算法。

55
00:03:22,810 --> 00:03:25,170
所以，讓我們的名單重置。

56
00:03:35,210 --> 00:03:37,750
歸併排序的過程中，有2個大的步驟。

57
00:03:37,750 --> 00:03:41,500
首先，連續分裂列表杯分為兩半

58
00:03:41,500 --> 00:03:44,860
直到我們有一堆名單，他們只用1杯。

59
00:03:44,860 --> 00:03:47,350
不要擔心，如果列表中包含一個奇數

60
00:03:47,350 --> 00:03:49,880
你不能讓他們之間的一個完全乾淨的切割。

61
00:03:49,880 --> 00:03:53,750
只需隨便挑哪一個清單，包括額外的杯子中。

62
00:03:53,750 --> 00:03:56,240
所以，讓我們這些列表拆分。

63
00:03:58,140 --> 00:04:01,310
現在，我們有2個列表。

64
00:04:04,120 --> 00:04:06,570
現在，我們有4個列表。

65
00:04:10,350 --> 00:04:13,870
>> 現在，我們有8個列表，每個列表中的單杯。

66
00:04:13,870 --> 00:04:16,630
所以這是它的第1步。

67
00:04:16,630 --> 00:04:22,230
對於第2步，我們多次合併對使用合併算法，我們以前學過的列表。

68
00:04:22,230 --> 00:04:29,160
合併108和15，我們結束了15日，108。

69
00:04:30,330 --> 00:04:36,250
，合併50和4，我們最終有4個，50。

70
00:04:36,960 --> 00:04:41,400
合併8和42，我們有8個，42。

71
00:04:42,790 --> 00:04:48,130
合併23和16，我們最終有16個，23。

72
00:04:49,740 --> 00:04:52,450
現在我們的列表大小為2。

73
00:04:53,020 --> 00:04:56,180
請注意，每個的4列出的是排序條件。

74
00:04:56,180 --> 00:04:59,160
>> 因此，我們可以再次開始合併對列表。

75
00:04:59,160 --> 00:05:03,240
合併15和108以及4和50  - 

76
00:05:03,240 --> 00:05:11,170
先來的4個，然後是15，然後是50，然後是108。

77
00:05:11,170 --> 00:05:15,120
合併8，42，16，23，

78
00:05:15,120 --> 00:05:22,440
我們先來的8個，然後16，然後23，然後42。

79
00:05:22,440 --> 00:05:27,370
所以現在我們有2列出了大小為4，每一個排序。

80
00:05:27,370 --> 00:05:30,980
所以，現在我們合併這兩個列表。

81
00:05:30,980 --> 00:05:33,440
首先，我們採取了4。

82
00:05:33,440 --> 00:05:36,580
然後，我們採取了8。

83
00:05:36,580 --> 00:05:50,700
然後我們把15和16，然後23，然後42，然後50，然後108。

84
00:05:50,700 --> 00:05:52,220
我們就大功告成了。

85
00:05:52,220 --> 00:05:54,900
我們現在有一個排序的列表。

86
00:05:54,900 --> 00:05:57,890
因此，如何快速是這樣的，到底是什麼？

87
00:05:57,890 --> 00:06:02,000
在技​​術方面，歸併排序是O（n日誌n），

88
00:06:02,000 --> 00:06:07,380
而所有的冒泡排序，插入排序，選擇排序為O（n²）。

89
00:06:07,380 --> 00:06:11,120
事實上，你會學習很快，你將不能夠拿出一種

90
00:06:11,120 --> 00:06:14,820
執行在一般情況下比O（n日誌n）。

91
00:06:14,820 --> 00:06:19,120
再次，不要擔心這個大O表示法，如果你還沒有看到它。

92
00:06:19,120 --> 00:06:23,490
>> 只知道，這意味著如果我們想要，排序一個真正的大名單

93
00:06:23,490 --> 00:06:26,820
冒泡排序，插入排序，選擇排序可能

94
00:06:26,820 --> 00:06:29,500
明顯長於合併排序。

95
00:06:29,500 --> 00:06:33,210
這並不意味著會更快歸併排序的所有列表

96
00:06:33,210 --> 00:06:36,220
甚至是任何單獨的列表中下一個一定規模的。

97
00:06:36,220 --> 00:06:41,950
例如，插入排序可能是最快的排序為所有小於5個元素的列表。

98
00:06:41,950 --> 00:06:47,360
在實踐中，合併排序通常更快盡可能小為50個元素的列表。

99
00:06:47,360 --> 00:06:51,120
>> 但這些額外的速度不會沒有代價的。

100
00:06:51,120 --> 00:06:54,770
與其他各種不同的是，一個列表，修改列表中的地方

101
00:06:54,770 --> 00:06:58,740
直到我們得到一個排序的列表，歸併排序需要一些額外的空間

102
00:06:58,740 --> 00:07:00,900
合併2列出了一起。

103
00:07:00,900 --> 00:07:04,690
我們不能立即使用的名單，被合併存儲合併列表

104
00:07:04,690 --> 00:07:08,880
因為我們可能會覆蓋仍需要合併的元素。

105
00:07:08,880 --> 00:07:13,540
這個空間是一個位的價格，但它通常是不講理的。

106
00:07:13,540 --> 00:07:15,330
這就是歸併排序。

107
00:07:15,330 --> 00:07:18,490
>> 我的名字是羅布·波頓，這是CS50。

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
 - 選擇排序。

110
00:07:24,000 --> 00:07:25,880
[笑]

111
00:07:25,880 --> 00:07:31,480
哦，得了採取的太多，因為我交換，我是如何呈現它。

112
00:07:31,480 --> 00:07:35,680
在左側的列表。這是一個錯字。

113
00:07:35,680 --> 00:07:39,290
[misspoke我搞砸了 - 

114
00:07:39,290 --> 00:07:41,190
[笑]

115
00:07:41,190 --> 00:07:44,190
我不知道是什麼 -