1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Сортировка слиянием]

2
00:00:02,000 --> 00:00:04,000
[Rob Боуден - Гарвардский университет]

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
Это означает, что если окончательный список содержит номера п, где п здесь 8,

51
00:03:08,070 --> 00:03:12,610
Затем нам нужно не более п сравнений, чтобы получить все эти цифры в правильном месте.

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
Итак, теперь мы объединить эти 2 списка.

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 (п § п),

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 (п § п) в общем случае.

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
[Оговорился] я облажался -

114
00:07:39,290 --> 00:07:41,190
[Смеется]

115
00:07:41,190 --> 00:07:44,190
Я не знаю, что -