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
>> 道格·劳埃德：所以插入排序是另一种
算法，我们可以用它来一个数组排序。

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
所以2是下一个未排序
数组的元素。

32
00:01:33,470 --> 00:01:36,250
显然，前所属
五，所以我们是怎么做

33
00:01:36,250 --> 00:01:41,580
是那种举行两场预留第二，
移5以上，然后插入两个

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
而事实上6大于5，所以
我们甚至不需要做任何交换。

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
你必须改为每个n个元素
最多n个位置，每一次我们

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
而有点像发生了什么
与在实施例5和6，

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
三，三生经过两次的话，OK，
一个，两个和三个排序。

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个元素可能是N个位置，

78
00:03:51,854 --> 00:03:54,020
希望这给你
一个想法，最坏的情况下

79
00:03:54,020 --> 00:03:57,770
运行时间为n的大澳方。

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
因此，在最好的情况下，它是n个欧米茄。

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