1
00:00:00,000 --> 00:00:02,826
>> [Играет музыка]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> ДАГ Lloyd: Так вставки сортировки другой
Алгоритм можно использовать для сортировки массива.

4
00:00:09,370 --> 00:00:12,350
Идея этого алгоритма
это, чтобы построить свой отсортированный массив

5
00:00:12,350 --> 00:00:19,670
в месте, переминаясь элементы из
способ, как вы идете, чтобы освободить место.

6
00:00:19,670 --> 00:00:22,240
Это немного отличается
от выбора рода или пузыря

7
00:00:22,240 --> 00:00:25,460
рода, например, где
мы регулировки местоположения,

8
00:00:25,460 --> 00:00:26,910
где мы делаем свопы.

9
00:00:26,910 --> 00:00:29,760
>> В этом случае то, что мы на самом деле
делаете раздвижные элементы

10
00:00:29,760 --> 00:00:31,390
более, из пути.

11
00:00:31,390 --> 00:00:34,030
Как это алгоритм
работать в псевдокоде?

12
00:00:34,030 --> 00:00:37,646
Ну давайте просто произвольно сказать, что
Первый элемент массива сортируется.

13
00:00:37,646 --> 00:00:38,770
Мы строим ее на месте.

14
00:00:38,770 --> 00:00:42,660
>> Мы собираемся идти один элемент, в то время, и
строить и поэтому первое, что мы видим,

15
00:00:42,660 --> 00:00:43,890
это массив один элемент.

16
00:00:43,890 --> 00:00:47,720
И по определению, один
элемент массива сортируется.

17
00:00:47,720 --> 00:00:50,850
>> Тогда мы будем повторять этот процесс until--
мы будем повторять следующую процедуру

18
00:00:50,850 --> 00:00:52,900
пока все элементы не сортируются.

19
00:00:52,900 --> 00:00:57,770
Посмотрите на следующий несортированным элемента и
вставьте его в отсортированном части,

20
00:00:57,770 --> 00:01:01,209
путем сдвига необходимое количество
элементов из пути.

21
00:01:01,209 --> 00:01:03,750
Надеюсь, эта визуализация
поможет вам увидеть именно то, что

22
00:01:03,750 --> 00:01:05,980
происходит с вставки рода.

23
00:01:05,980 --> 00:01:08,010
>> Итак, еще раз, вот наш
Весь массив несортированный,

24
00:01:08,010 --> 00:01:10,970
все элементы отображаются в красном цвете.

25
00:01:10,970 --> 00:01:13,320
И давайте следовать
шаги нашего псевдокоде.

26
00:01:13,320 --> 00:01:16,970
Первое, что мы делаем, является мы называем
Первый элемент массива, отсортировать.

27
00:01:16,970 --> 00:01:20,920
Так что мы просто собираюсь говорить
пять, вы теперь сортируются.

28
00:01:20,920 --> 00:01:24,570
>> Затем мы рассмотрим на следующем
несортированный элемент массива

29
00:01:24,570 --> 00:01:27,610
и мы хотим, чтобы вставить, что
в части отсортировано,

30
00:01:27,610 --> 00:01:29,750
сдвигая элементы старше.

31
00:01:29,750 --> 00:01:33,470
Так два это следующий несортированный
элемент массива.

32
00:01:33,470 --> 00:01:36,250
Очевидно, он принадлежит до
пять, так что мы собираемся сделать

33
00:01:36,250 --> 00:01:41,580
является своего рода проведет два в сторону на секунду,
переложить пять над, а затем вставьте два

34
00:01:41,580 --> 00:01:43,210
до пяти, где должны идти.

35
00:01:43,210 --> 00:01:45,280
И теперь мы можем сказать, что два сортируется.

36
00:01:45,280 --> 00:01:48,400
>> Итак, как вы видите, мы только пока
посмотрел на двух элементов массива.

37
00:01:48,400 --> 00:01:50,600
Мы не смотрели на
отдых на всех, но мы

38
00:01:50,600 --> 00:01:54,582
получил эти два элемента сортируются по
Способ механизма переключения.

39
00:01:54,582 --> 00:01:56,410
>> Таким образом, мы повторяем процесс снова.

40
00:01:56,410 --> 00:01:58,850
Посмотрите на следующий несортированный
элемент, что одна.

41
00:01:58,850 --> 00:02:04,010
Давайте считать, что в сторону на секунду,
переложить все закончилось, и положить один

42
00:02:04,010 --> 00:02:05,570
где она должна идти.

43
00:02:05,570 --> 00:02:08,110
>> Опять же, до сих пор, мы только когда-либо
посмотрел на один, два и пять.

44
00:02:08,110 --> 00:02:12,480
Мы не знаем, что еще идет,
но мы сортируются эти три элемента.

45
00:02:12,480 --> 00:02:16,030
>> Следующая несортированный элемент
три, так что мы будем устанавливать его в сторону.

46
00:02:16,030 --> 00:02:18,200
Мы постепенно смещать то, что мы
нужно, который, на этот раз

47
00:02:18,200 --> 00:02:21,820
это еще не все, как и в предыдущем
два случая, это просто пять.

48
00:02:21,820 --> 00:02:25,440
И тогда мы будем придерживаться три в,
между двумя и пятью.

49
00:02:25,440 --> 00:02:27,849
>> Шесть является следующим несортированный
элемент к массиву.

50
00:02:27,849 --> 00:02:31,140
И в самом деле шести больше пяти, так
мы даже не нужно делать какие-либо замены.

51
00:02:31,140 --> 00:02:35,710
Мы можем просто лавировать шесть право на
конец отсортированного части.

52
00:02:35,710 --> 00:02:38,270
>> Наконец, четыре является
Последнее несортированный элемент.

53
00:02:38,270 --> 00:02:42,060
Таким образом, мы будем устанавливать его в сторону, перейти по
элементы, которые мы должны перенести в течение,

54
00:02:42,060 --> 00:02:43,780
а затем положить четыре, где она принадлежит.

55
00:02:43,780 --> 00:02:46,400
А теперь посмотрите, мы вроде
из всех элементов.

56
00:02:46,400 --> 00:02:48,150
Обратите внимание, с введением
сортировать, у нас не было

57
00:02:48,150 --> 00:02:50,240
чтобы идти вперед и назад через массив.

58
00:02:50,240 --> 00:02:54,720
Мы только пошли через массив
одно время, и мы перешли вещи

59
00:02:54,720 --> 00:02:59,870
что мы уже сталкивались в порядок
чтобы освободить место для новых элементов.

60
00:02:59,870 --> 00:03:02,820
>> Так что в худшем случае
Сценарий с вставки рода?

61
00:03:02,820 --> 00:03:05,090
В худшем случае,
массив в обратном порядке.

62
00:03:05,090 --> 00:03:11,180
Вы должны перейти каждого из п элементов
до н позиций, каждый раз, когда мы

63
00:03:11,180 --> 00:03:12,880
сделать вставку.

64
00:03:12,880 --> 00:03:15,720
Это много меняется.

65
00:03:15,720 --> 00:03:18,014
>> В лучшем случае,
Массив прекрасно отсортированы.

66
00:03:18,014 --> 00:03:20,680
И вроде как то, что произошло
с пятью и шестью в примере,

67
00:03:20,680 --> 00:03:23,779
где мы могли бы просто лавировать ее на
без того, чтобы сделать любой сдвиг,

68
00:03:23,779 --> 00:03:24,820
мы, по существу, что делать.

69
00:03:24,820 --> 00:03:27,560
>> Если представить, что наши
Массив был один через шесть,

70
00:03:27,560 --> 00:03:29,900
мы бы начать с
заявив, один сортируется.

71
00:03:29,900 --> 00:03:33,300
Два приходит после одного, чтобы мы могли просто
говорят, хорошо, хорошо один и два сортируются.

72
00:03:33,300 --> 00:03:36,190
Три приходит после двух, так, хорошо,
один и два, и три сортируются.

73
00:03:36,190 --> 00:03:39,590
>> Мы не делаем никаких свопы, мы
просто перемещение эту произвольную линию

74
00:03:39,590 --> 00:03:42,460
между сортируются и несортированный, как мы идем.

75
00:03:42,460 --> 00:03:46,646
Как эффективно, как мы это делали в примере,
поворачивая элементы синий, как мы дальше.

76
00:03:46,646 --> 00:03:48,270
Так что в худшем случае выполнения, то?

77
00:03:48,270 --> 00:03:51,854
Помните, что если у нас есть переложить каждый из
русские элементы, возможно, N позиций,

78
00:03:51,854 --> 00:03:54,020
мы надеемся, что дает вам
идея, что в худшем случае

79
00:03:54,020 --> 00:03:57,770
выполнения является Большой О п квадрате.

80
00:03:57,770 --> 00:04:00,220
>> Если массив прекрасно
сортировать, все, что мы должны сделать,

81
00:04:00,220 --> 00:04:04,480
это посмотреть на каждого элемента
один раз, а затем мы сделали.

82
00:04:04,480 --> 00:04:08,440
Таким образом, в лучшем случае, это омега п.

83
00:04:08,440 --> 00:04:09,490
>> Я Дуг Ллойд.

84
00:04:09,490 --> 00:04:11,760
Это CS50.

85
00:04:11,760 --> 00:04:13,119