1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> ДАГ Lloyd: Так в CS50 мы узнали о
разнообразие сортировки и поиска

3
00:00:08,900 --> 00:00:09,442
алгоритмы.

4
00:00:09,442 --> 00:00:11,400
И иногда это может быть
немного сложнее держать

5
00:00:11,400 --> 00:00:14,161
трек, какой алгоритм делает.

6
00:00:14,161 --> 00:00:15,910
Мы действительно только
обезжиренное поверхность тоже

7
00:00:15,910 --> 00:00:18,740
Есть много других поиск
и алгоритмы сортировки.

8
00:00:18,740 --> 00:00:21,780
Таким образом, в этом видео давайте
просто взять несколько минут

9
00:00:21,780 --> 00:00:24,980
чтобы попытаться отогнать каждый алгоритм
до его основных элементов

10
00:00:24,980 --> 00:00:27,810
так что вы можете помнить, наиболее
важная информация о них

11
00:00:27,810 --> 00:00:31,970
и быть в состоянии сформулировать
различия, если это необходимо.

12
00:00:31,970 --> 00:00:34,220
>> Первый выбор рода.

13
00:00:34,220 --> 00:00:38,210
Основная идея выбора рода
это найти наименьший элемент несортированный

14
00:00:38,210 --> 00:00:42,890
в массиве и поменять его с
в первую очередь несортированный элемент этого массива.

15
00:00:42,890 --> 00:00:46,620
Мы сказали, что в худшем случае
запустить время, что был н квадрате.

16
00:00:46,620 --> 00:00:50,060
И если вы хотите, чтобы вспомнить, почему, взять
Посмотрите на выбор рода видео.

17
00:00:50,060 --> 00:00:54,560
Время работы лучшем случае
также п квадрате.

18
00:00:54,560 --> 00:00:58,910
>> Пузырь рода, идея, что
один, чтобы поменять соседние пары.

19
00:00:58,910 --> 00:01:01,730
Так что это ключ, который помогает вам
запомнить разницу здесь.

20
00:01:01,730 --> 00:01:04,920
Выбор рода есть, до сих пор,
найти smallest-- пузырь

21
00:01:04,920 --> 00:01:06,790
Сортировать вне поменять соседние пары.

22
00:01:06,790 --> 00:01:08,710
Мы поменять соседние пары
элементов, если они

23
00:01:08,710 --> 00:01:12,530
вышли из строя, который эффективно
пузыри крупные элементы права,

24
00:01:12,530 --> 00:01:17,060
и в то же время она также начинает
для перемещения мелких элементов влево.

25
00:01:17,060 --> 00:01:20,180
Время выполнения случай наихудшего случая
пузыря сортировки п квадрате.

26
00:01:20,180 --> 00:01:23,476
Время работы лучшем случае
пузыря сортировки п.

27
00:01:23,476 --> 00:01:25,350
Потому что в этой ситуации
мы не actually--

28
00:01:25,350 --> 00:01:27,141
мы, возможно, не нужно
делать какие-либо свопы на всех.

29
00:01:27,141 --> 00:01:31,026
У нас есть только сделать один
пройти через все п элементов.

30
00:01:31,026 --> 00:01:34,600
>> В вставки рода, то
Основная идея здесь меняется.

31
00:01:34,600 --> 00:01:36,630
Это ключевое слово для вставки рода.

32
00:01:36,630 --> 00:01:39,630
Мы собираемся выйти один раз через
массив слева направо.

33
00:01:39,630 --> 00:01:41,670
И, как мы делаем, мы
собирается перенести элементы

34
00:01:41,670 --> 00:01:46,260
мы уже видели, чтобы освободить место для
мелкие, что нужно, чтобы соответствовать где-то

35
00:01:46,260 --> 00:01:48,080
назад в этой отсортировано части.

36
00:01:48,080 --> 00:01:51,600
Так мы строим отсортированный массив одним
элемент, в то время, слева направо,

37
00:01:51,600 --> 00:01:54,740
и мы переходим вещи, чтобы сделать комнату.

38
00:01:54,740 --> 00:01:58,650
Наихудший время пробег
вставка сортировки п квадрате.

39
00:01:58,650 --> 00:02:02,380
Время лучший вариант запуска является н.

40
00:02:02,380 --> 00:02:05,380
>> Слияние sort-- ключевого слова
здесь разделение и слияние.

41
00:02:05,380 --> 00:02:08,949
Мы разделили полный спектр ли
это шесть элементов, восьми элементов,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- мы разделили его
сократилась вдвое, вдвое, вдвое,

43
00:02:13,790 --> 00:02:17,720
пока у нас под массив
н одной массивов элементов.

44
00:02:17,720 --> 00:02:19,470
Набор N Один массивов элементов.

45
00:02:19,470 --> 00:02:22,640
Итак, мы начали с одной
Массив 1000 элемент,

46
00:02:22,640 --> 00:02:26,550
и мы добраться до точки, где мы
есть 1000 массивов одноэлементные.

47
00:02:26,550 --> 00:02:30,990
Тогда мы начинаем объединить эти суб массивы
вместе в правильном порядке.

48
00:02:30,990 --> 00:02:34,860
Таким образом, мы принять два массива одноэлементные
и создать массив из двух элементов.

49
00:02:34,860 --> 00:02:38,180
Возьмем два массивы двух элементов
и создать массив из четырех элементов

50
00:02:38,180 --> 00:02:43,900
и так далее, и так далее, пока мы не
снова восстановлен один массив п элементов.

51
00:02:43,900 --> 00:02:48,410
>> Наихудший время пробег
сортировка слиянием п раз войти н.

52
00:02:48,410 --> 00:02:52,390
У нас есть п элементов, но
этот процесс рекомбинирующий

53
00:02:52,390 --> 00:02:56,960
принимает войти п шагов, чтобы получить
вернуться к полной массива.

54
00:02:56,960 --> 00:03:01,160
В лучшем случае время выполнения также п журнала
п потому что этот процесс не имеет большого

55
00:03:01,160 --> 00:03:04,090
заботиться, был ли массив
сортировки или не начинать.

56
00:03:04,090 --> 00:03:07,590
Процесс тот же, есть
нет способ коротких вещей выключателей.

57
00:03:07,590 --> 00:03:11,610
Так п п войти в худшем случае,
п п войти в лучшем случае.

58
00:03:11,610 --> 00:03:13,960
>> Мы говорили о двух
алгоритмы поиска.

59
00:03:13,960 --> 00:03:16,230
Так линейный поиск о итерации.

60
00:03:16,230 --> 00:03:19,500
Перейдем через массив
один раз, слева направо,

61
00:03:19,500 --> 00:03:21,950
пытаясь найти номер
что мы ищем.

62
00:03:21,950 --> 00:03:24,550
Время худший запустить большой вывода п.

63
00:03:24,550 --> 00:03:27,610
Это может занять нам итерации
по каждой элемента

64
00:03:27,610 --> 00:03:30,660
чтобы найти элемент мы ищем
для, либо в последней позиции,

65
00:03:30,660 --> 00:03:31,630
или не на всех.

66
00:03:31,630 --> 00:03:34,720
Но мы не можем подтвердить, что до тех пор,
мы смотрели на все.

67
00:03:34,720 --> 00:03:36,730
м лучшем случае, мы сразу найти.

68
00:03:36,730 --> 00:03:41,060
Лучший случая время пробег
линейный поиск омега 1.

69
00:03:41,060 --> 00:03:43,689
>> Наконец, было бинарный поиск,
который требует ассорти массив.

70
00:03:43,689 --> 00:03:45,605
Помните, что это очень
важным фактором

71
00:03:45,605 --> 00:03:47,155
при работе с бинарного поиска.

72
00:03:47,155 --> 00:03:50,180
Это является необходимым условием для помощи it--
массив, что вы ищете через

73
00:03:50,180 --> 00:03:52,160
должны быть отсортированы.

74
00:03:52,160 --> 00:03:54,500
В противном случае, ключевое слово
это разделяй и властвуй.

75
00:03:54,500 --> 00:03:58,310
Сплит массив пополам и
устранения половина элементов

76
00:03:58,310 --> 00:04:00,780
каждый раз, как вы пройти через.

77
00:04:00,780 --> 00:04:04,330
Из-за этого разделяй и властвуй
и разделение вещей в половине подхода,

78
00:04:04,330 --> 00:04:07,450
в худшем случае время выполнения
бинарных поиск

79
00:04:07,450 --> 00:04:11,730
войти н, который, по существу
лучше, чем линейный поиск в п.

80
00:04:11,730 --> 00:04:13,570
Время лучшем случае работать по-прежнему один.

81
00:04:13,570 --> 00:04:17,010
>> Мы могли бы сразу же найти
Первый раз мы делаем разделение, но,

82
00:04:17,010 --> 00:04:19,339
снова, помните, что
хотя двоичный поиск

83
00:04:19,339 --> 00:04:24,030
значительно лучше, чем линейный поиск
в силу того, журнал N по сравнению с п,

84
00:04:24,030 --> 00:04:27,110
Вы, возможно, придется пройти через работу
сортировки свой массив первой,

85
00:04:27,110 --> 00:04:32,010
может сделать его менее эффективным в зависимости
на размер итерации отсортированы.

86
00:04:32,010 --> 00:04:35,250
>> Я Дуг Ллойд, это CS50.

87
00:04:35,250 --> 00:04:36,757