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
哦，我們這樣做 - “”轟！“