1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [插入排序]

2
00:00:02,290 --> 00:00:04,240
[和汤米MacWilliam] [哈佛大学]

3
00:00:04,240 --> 00:00:07,290
[这是CS50.TV]

4
00:00:07,290 --> 00:00:13,060
让我们来看看插入排序，算法的号码列表和排序。

5
00:00:13,060 --> 00:00:18,300
简单的算法，记住，是一步一步的过程来完成任务。

6
00:00:18,300 --> 00:00:23,640
后面插入排序的基本思想，是将我们的名单分为两部分，

7
00:00:23,640 --> 00:00:26,580
一个的排序部分和未排序的部分。

8
00:00:26,580 --> 00:00:29,290
>> 该算法在每个步骤中，一个数字移动

9
00:00:29,290 --> 00:00:32,439
在未排序的部分排序的部分

10
00:00:32,439 --> 00:00:35,680
直到最后整个列表进行排序。

11
00:00:35,680 --> 00:00:43,340
这里是六个未排序的数字列表 -  23，42，4，16，8，和15。

12
00:00:43,340 --> 00:00:47,680
因为这些数字是不是所有的升序排列，它们排序。

13
00:00:47,680 --> 00:00:53,890
因为我们还没有开始整理，我们会考虑所有的六大要素，我们未分类的部分。

14
00:00:53,890 --> 00:00:59,270
>> 一旦我们开始整理，我们把这些排序的数字，剩下的这些。

15
00:00:59,270 --> 00:01:03,600
所以，让我们开始有23个，在列表中的第一个元素。

16
00:01:03,600 --> 00:01:06,930
我们没有尚未我们的排序部中的任何元素，

17
00:01:06,930 --> 00:01:12,460
让我们简单地认为23是我们的排序部分的开始和结束的。

18
00:01:12,460 --> 00:01:16,510
现在，我们的排序部分有一个数字，23，

19
00:01:16,510 --> 00:01:20,260
我们未分类的部分有这五个数字。

20
00:01:20,260 --> 00:01:27,320
现在让我们插入到我们的未分类的部分，42岁，在未来数排序的部分。

21
00:01:27,320 --> 00:01:35,930
>> 要做到这一点，我们需要比较的42到23  - 到目前为止，我们的排序部分中的唯一元素。

22
00:01:35,930 --> 00:01:41,980
四是大于23，所以我们可以简单地追加42月底

23
00:01:41,980 --> 00:01:45,420
的排序的列表中的部分。太好了！

24
00:01:45,420 --> 00:01:51,850
现在，我们的排序部分也有两个元素，我们未分类的部分有四个元素。

25
00:01:51,850 --> 00:01:57,200
所以，现在让我们转移到了4，未排序的部分中的下一个元素。

26
00:01:57,200 --> 00:02:00,230
所以，这应该被放置在排序部？

27
00:02:00,230 --> 00:02:04,220
>> 请记住，我们想要把这个数的排序顺序

28
00:02:04,220 --> 00:02:08,680
因此，在任何时候，我们的排序部分保持正确排序。

29
00:02:08,680 --> 00:02:14,380
如果我们把4个到42个的权利，那么我们的名单将出。

30
00:02:14,380 --> 00:02:18,380
所以，让我们继续在我们的排序部分从右到左移动。

31
00:02:18,380 --> 00:02:23,260
随着我们的，让我们每个号码转移下来的地方以腾出空间给新的号码。

32
00:02:25,440 --> 00:02:31,740
好了，4也是小于23，因此，我们不能把它在这里。

33
00:02:31,740 --> 00:02:34,480
让我们继续前进的23个正确的地方。

34
00:02:36,500 --> 00:02:43,120
>> 这意味着我们想放置4到第一个插槽的排序部分。

35
00:02:43,120 --> 00:02:46,300
请注意，这个空间是如何在列表中已经是空的，

36
00:02:46,300 --> 00:02:51,120
因为我们一直在移动排序的元素，因为我们已经遇到他们。

37
00:02:51,120 --> 00:02:52,740
好的。因此，我们已经完成一半了。

38
00:02:52,740 --> 00:02:57,990
让我们继续我们的算法插入16到排序的部分。

39
00:02:59,260 --> 00:03:03,820
16为小于42，所以让我们转移42至正确的。

40
00:03:05,700 --> 00:03:10,190
16为小于23，所以我们也该元素的转移。

41
00:03:11,790 --> 00:03:20,820
>> 现在，图16是大于4。因此，它看起来像我们想在4和23之间插入16。

42
00:03:20,820 --> 00:03:24,620
通过排序的列表部移动的同时，由右至左，

43
00:03:24,620 --> 00:03:29,160
4是第一个数字，我们已经看到，数小于

44
00:03:29,160 --> 00:03:31,540
我们正在试图插入。

45
00:03:31,540 --> 00:03:35,820
所以，现在我们可以插入16到这个空的插槽，

46
00:03:35,820 --> 00:03:40,520
请记得，我们已经创建了移动的元素在排序部分

47
00:03:40,520 --> 00:03:43,340
我们遇到他们。

48
00:03:43,340 --> 00:03:47,900
>> 好的。现在，我们有四个排序的元素和两个未排序的元素。

49
00:03:47,900 --> 00:03:51,600
所以，让我们继续前进8成排序的部分。

50
00:03:51,600 --> 00:03:55,010
八是小于42。

51
00:03:55,010 --> 00:03:56,940
八是小于23。

52
00:03:56,940 --> 00:04:00,230
和图8是小于16。

53
00:04:00,230 --> 00:04:03,110
但是，图8是大于4。

54
00:04:03,110 --> 00:04:07,280
所以，我们想在4和16之间插入8。

55
00:04:09,070 --> 00:04:13,650
现在，我们只是有一个更多的元素进行排序 -  15。

56
00:04:13,950 --> 00:04:16,589
十五是小于42，

57
00:04:16,589 --> 00:04:19,130
十五是小于23。

58
00:04:19,130 --> 00:04:21,750
和15是小于16。

59
00:04:21,750 --> 00:04:24,810
但15是大于8。

60
00:04:24,810 --> 00:04:27,440
>> 所以，在这里我们想使我们的最后插入。

61
00:04:28,770 --> 00:04:30,330
我们就大功告成了。

62
00:04:30,330 --> 00:04:33,540
我们有没有更多的元素在未排序的部分，

63
00:04:33,540 --> 00:04:36,670
和我们的排序条件部分是在以正确的顺序。

64
00:04:36,670 --> 00:04:40,270
从最小到最大的数字是有序的。

65
00:04:40,270 --> 00:04:44,330
所以，让我们来看看一些伪代码描述的步骤，我们只是执行。

66
00:04:46,760 --> 00:04:51,740
>> 在第1行中，我们可以看到，我们需要遍历列表中的每个元素

67
00:04:51,740 --> 00:04:57,060
除了第一个，因为第一个元素在未排序的部分，都只是

68
00:04:57,060 --> 00:05:00,220
的排序部中的第一元素。

69
00:05:00,220 --> 00:05:06,320
在第2和第3行，我们正在跟踪我们目前在未排序的部分。

70
00:05:06,320 --> 00:05:10,450
元素代表的数量，我们目前正在进入排序的部分，

71
00:05:10,450 --> 00:05:15,600
j表示我们的索引中未排序的部分。

72
00:05:15,600 --> 00:05:20,980
>> 在第4行中，我们遍历由右至左排序的部分。

73
00:05:20,980 --> 00:05:26,010
我们要停止迭代一次的元素的左侧我们当前的位置

74
00:05:26,010 --> 00:05:30,050
是小于我们试图插入的元素。

75
00:05:30,050 --> 00:05:35,600
在第5行中，我们把每一个元素我们遇到的一个空间，以正确的。

76
00:05:35,600 --> 00:05:40,950
这样一来，当我们找到的第一个元素，我们将有一个明确的空间插入到

77
00:05:40,950 --> 00:05:44,080
不到我们正在元素。

78
00:05:44,080 --> 00:05:50,800
在第6行，我们正在更新我们的柜台，继续向左移动通过排序的部分。

79
00:05:50,800 --> 00:05:56,860
最后，第7行，我们的元素插入到列表中的排序部分。

80
00:05:56,860 --> 00:06:00,020
>> 我们知道它的好插入位置j，

81
00:06:00,020 --> 00:06:05,360
因为我们已经提出的元素，以前是有一个空格的右侧。

82
00:06:05,360 --> 00:06:09,460
请记住，我们正在通过由右至左排序的部分，

83
00:06:09,460 --> 00:06:13,960
但我们正在通过未排序的部分由左到右。

84
00:06:13,960 --> 00:06:19,090
好的。现在，让我们来看看在多长时间运行的算法了。

85
00:06:19,090 --> 00:06:25,300
多久需要运行这个算法在最坏的情况下，我们首先会问的问题。

86
00:06:25,300 --> 00:06:29,040
回想一下，我们与大O表示法表示这个运行时间。

87
00:06:32,530 --> 00:06:38,500
为了我们的列表进行排序，我们不得不遍历未排序的部分中的元素，

88
00:06:38,500 --> 00:06:43,430
并为每个这些元素，可能超过的排序部中的所有元素的。

89
00:06:43,430 --> 00:06:47,950
直观地说，这听起来像一个O（N ^ 2）操作。

90
00:06:47,950 --> 00:06:51,840
>> 在我们的伪代码，我们有一个循环嵌套在另一个循环，

91
00:06:51,840 --> 00:06:55,290
而事实上，听起来像一个O（N ^ 2）操作。

92
00:06:55,290 --> 00:07:01,590
然而，排序的部分列表中没有包含整个列表，直到最后一刻。

93
00:07:01,590 --> 00:07:06,920
尽管如此，我们可能在开始的时候排序的部分中插入一个新元素

94
00:07:06,920 --> 00:07:09,320
在每次迭代的算法，

95
00:07:09,320 --> 00:07:14,500
这意味着我们不得不看每个元素目前在已排序的部分。

96
00:07:14,500 --> 00:07:20,090
所以，这意味着我们有可能做一个比较的第二个元素，

97
00:07:20,090 --> 00:07:24,660
两个比较的第三个元素，依此类推。

98
00:07:24,660 --> 00:07:32,480
所以，总的步数是从1到的列表的长度减1的整数的总和。

99
00:07:32,480 --> 00:07:35,240
我们可以代表这一个总和。

100
00:07:41,170 --> 00:07:47,270
>> 在这里，我们不会去求和，但事实证明，这个总和是相等的

101
00:07:47,270 --> 00:07:57,900
超过2 N（n  -  1个），这相当于n ^ 2的/ 2  -  n / 2个。

102
00:07:57,900 --> 00:08:00,800
在谈到关于渐近运行时，

103
00:08:00,800 --> 00:08:05,170
这n ^ 2项将主宰这n个任期。

104
00:08:05,170 --> 00:08:11,430
所以，插入排序是大O（N ^ 2）。

105
00:08:11,430 --> 00:08:16,150
如果我们遇到一个已排序的列表中插入排序。

106
00:08:16,150 --> 00:08:20,960
在这种情况下，我们只需要建立从左至右排序的部分。

107
00:08:20,960 --> 00:08:25,050
所以，我们只需要n个步骤的顺序。

108
00:08:25,050 --> 00:08:29,740
>> 这意味着，插入排序的n有一个最好的情况下的性能，

109
00:08:29,740 --> 00:08:34,130
我们与Ω（n）的代表。

110
00:08:34,130 --> 00:08:36,190
这就是它插入排序，

111
00:08:36,190 --> 00:08:40,429
只是我们的许多算法可以对列表进行排序。

112
00:08:40,429 --> 00:08:43,210
我的名字是汤米，这是CS50。

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
啊，你只是不能停止，一旦它开始。

115
00:09:01,620 --> 00:09:04,760
哦，我们这样做 - “”轰！“