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
我不知道是什么 -