1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY：讓我們來看看在選擇排序的算法

2
00:00:09,980 --> 00:00:12,800
的號碼列表和排序。

3
00:00:12,800 --> 00:00:15,750
一種算法，記住，是一個簡單的一步一步的

4
00:00:15,750 --> 00:00:18,370
完成任務的過程。

5
00:00:18,370 --> 00:00:21,470
選擇排序的基本理念是將

6
00:00:21,470 --> 00:00:23,390
我們的名單分為兩部分 - 

7
00:00:23,390 --> 00:00:26,810
一個的排序部分和未排序的部分。

8
00:00:26,810 --> 00:00:30,200
該算法在每個步驟中，一個數字移動從

9
00:00:30,200 --> 00:00:33,800
直到最後的排序條件部分的未分類的部分

10
00:00:33,800 --> 00:00:35,880
整個列表進行排序。

11
00:00:35,880 --> 00:00:38,510
所以這裡有一個列表中的六個數字 - 

12
00:00:38,510 --> 00:00:44,010
23，42，4，16，8，和15。

13
00:00:44,010 --> 00:00:47,680
現在被認為是整個列表排序。

14
00:00:47,680 --> 00:00:51,770
即使16這樣的數字可能已經在其正確的

15
00:00:51,770 --> 00:00:56,040
位置，我們的算法有沒有辦法知道，直到

16
00:00:56,040 --> 00:00:57,980
整個列表進行排序。

17
00:00:57,980 --> 00:01:01,355
因此，我們會考慮每一個數字無序的，直到我們整理

18
00:01:01,355 --> 00:01:03,800
它自己。

19
00:01:03,800 --> 00:01:06,890
我們知道，我們要以升序排列的列表。

20
00:01:06,890 --> 00:01:10,200
因此，我們將要建立我們的名單的排序部分

21
00:01:10,200 --> 00:01:13,280
由左到右，從最小到最大。

22
00:01:13,280 --> 00:01:17,970
要做到這一點，我們需要找到最小的未分類的元素

23
00:01:17,970 --> 00:01:21,350
並把它在排序的部分結束。

24
00:01:21,350 --> 00:01:25,370
由於此列表未排序，只有這樣，才能做到這一點是

25
00:01:25,370 --> 00:01:29,330
看在未排序的部分，記憶中的每個元素

26
00:01:29,330 --> 00:01:32,010
哪一個元素是最低的和比較

27
00:01:32,010 --> 00:01:33,770
每個元素。

28
00:01:33,770 --> 00:01:36,150
因此，我們將首先在23。

29
00:01:36,150 --> 00:01:38,650
這是我們所見過的第一個元素，所以我們會記住

30
00:01:38,650 --> 00:01:40,050
它作為最低。

31
00:01:40,050 --> 00:01:42,320
接下來，我們看42。

32
00:01:42,320 --> 00:01:46,720
42是大於23，所以23仍然是最低。

33
00:01:46,720 --> 00:01:51,210
其次是4，這是小於23，所以我們會記住4

34
00:01:51,210 --> 00:01:52,880
作為新的最小值。

35
00:01:52,880 --> 00:01:56,380
接下來是16，這是大於4，所以4

36
00:01:56,380 --> 00:01:57,980
仍然是最低。

37
00:01:57,980 --> 00:02:03,670
圖8是大於4，和圖15是大於4，所以4必須是

38
00:02:03,670 --> 00:02:05,980
最小的未分類的元素。

39
00:02:05,980 --> 00:02:09,350
因此，即使作為人類，我們可以立即看到，4

40
00:02:09,350 --> 00:02:12,300
最小的元素，我們的算法需要看

41
00:02:12,300 --> 00:02:15,710
每一個未排序的元素，即使我們已經找到了4  - 

42
00:02:15,710 --> 00:02:16,860
最小的元素。

43
00:02:16,860 --> 00:02:19,900
所以，現在，我們已經發現的最小元素，4，我們將要

44
00:02:19,900 --> 00:02:23,410
將它移動到列表的排序部。

45
00:02:23,410 --> 00:02:27,320
由於這是第一個步驟中，這意味著我們希望把4日

46
00:02:27,320 --> 00:02:29,680
在列表的開頭。

47
00:02:29,680 --> 00:02:33,040
現在圖23是在列表的開頭，所以

48
00:02:33,040 --> 00:02:36,080
讓我們交換的4個和23個。

49
00:02:36,080 --> 00:02:38,870
所以，現在我們的名單看起來是這樣的。

50
00:02:38,870 --> 00:02:42,710
我們知道，4必須是在其最終位置，因為它是

51
00:02:42,710 --> 00:02:45,890
兩個最小的元素和元素的開頭

52
00:02:45,890 --> 00:02:46,960
的列表。

53
00:02:46,960 --> 00:02:50,650
因此，這意味著，我們永遠不需要再次移動它。

54
00:02:50,650 --> 00:02:53,910
因此，讓我們重複此過程，添加另一個元素

55
00:02:53,910 --> 00:02:55,910
排序的列表中的部分。

56
00:02:55,910 --> 00:02:58,950
我們知道，我們並不需要，因為它是在4

57
00:02:58,950 --> 00:03:00,000
已經排序。

58
00:03:00,000 --> 00:03:03,540
因此，我們就可以開始的42個，我們會記住的

59
00:03:03,540 --> 00:03:05,290
最小的元素。

60
00:03:05,290 --> 00:03:08,700
所以接下來我們來看看23小於42，所以我們

61
00:03:08,700 --> 00:03:11,620
記得23是新的最低。

62
00:03:11,620 --> 00:03:14,870
接下來，我們看到這是小於23的16，所以

63
00:03:14,870 --> 00:03:16,800
16是新的最低。

64
00:03:16,800 --> 00:03:19,720
現在我們來看看在8小於16，所以

65
00:03:19,720 --> 00:03:21,130
圖8是新的最小值。

66
00:03:21,130 --> 00:03:25,900
和最後8是小於15，因此，我們知道，圖8是一個最小

67
00:03:25,900 --> 00:03:27,780
未分類的元素。

68
00:03:27,780 --> 00:03:30,660
因此，這意味著我們應該附加的排序

69
00:03:30,660 --> 00:03:32,450
列表中的部分。

70
00:03:32,450 --> 00:03:35,990
現在是唯一的排序元素，所以我們想要把

71
00:03:35,990 --> 00:03:38,410
接下來的8到4。

72
00:03:38,410 --> 00:03:41,920
由於42是第一要素，在未排序的部分

73
00:03:41,920 --> 00:03:47,260
名單中，我們將要交換42和8。

74
00:03:47,260 --> 00:03:49,680
所以，現在我們的名單看起來是這樣的。

75
00:03:49,680 --> 00:03:53,830
圖4和圖8表示排序的列表中的部分，並

76
00:03:53,830 --> 00:03:56,440
剩下的數字表示未分類的

77
00:03:56,440 --> 00:03:58,260
列表中的部分。

78
00:03:58,260 --> 00:04:00,630
因此，讓我們繼續進行下一次迭代。

79
00:04:00,630 --> 00:04:03,850
我們從23日的時間，因為我們不需要看

80
00:04:03,850 --> 00:04:05,770
在4和8了，因為他們已經

81
00:04:05,770 --> 00:04:07,660
已排序。

82
00:04:07,660 --> 00:04:10,270
16小於23，所以我們會記住

83
00:04:10,270 --> 00:04:12,070
16作為新的最小值。

84
00:04:12,070 --> 00:04:18,149
圖16是小於42，但圖15是小於16，所以15必須是

85
00:04:18,149 --> 00:04:20,480
最低未分類的元素。

86
00:04:20,480 --> 00:04:24,580
所以，現在我們要交換15日和23日至

87
00:04:24,580 --> 00:04:26,310
在此給我們的清單。

88
00:04:26,310 --> 00:04:30,500
已排序的列表中的部分由4，8和15，以及

89
00:04:30,500 --> 00:04:33,210
這些元素依然排序。

90
00:04:33,210 --> 00:04:36,900
但它只是恰巧下一個未排序的元素，16，

91
00:04:36,900 --> 00:04:38,480
已經排序。

92
00:04:38,480 --> 00:04:42,060
然而，有沒有辦法知道我們的算法，16

93
00:04:42,060 --> 00:04:45,230
已經在正確的位置，所以我們仍然需要

94
00:04:45,230 --> 00:04:47,870
重複完全相同的相同的過程。

95
00:04:47,870 --> 00:04:53,750
所以我們看到，圖16是小於42，和圖16是小於23，所以

96
00:04:53,750 --> 00:04:56,230
16必須的最小元素。

97
00:04:56,230 --> 00:04:59,010
交換這個元素本身，這是不可能的，所以我們可以

98
00:04:59,010 --> 00:05:01,780
簡單地離開這個位置。

99
00:05:01,780 --> 00:05:04,660
因此，我們需要一個更通過我們的算法。

100
00:05:04,660 --> 00:05:09,370
圖42是大於23，所以23必須是

101
00:05:09,370 --> 00:05:10,970
最低未分類的元素。

102
00:05:10,970 --> 00:05:17,410
一旦我們交換23和42，我們結束了我們的最終

103
00:05:17,410 --> 00:05:18,530
排序的列表 - 

104
00:05:18,530 --> 00:05:23,390
4，8，15，16，23，42。

105
00:05:23,390 --> 00:05:26,830
我們知道42必須在正確的地方，因為它是

106
00:05:26,830 --> 00:05:30,210
唯一的元素離開，這就是選擇排序。

107
00:05:30,210 --> 00:05:32,100
現在讓我們來規範我們的算法與一些

108
00:05:32,100 --> 00:05:34,540
偽代碼。

109
00:05:34,540 --> 00:05:37,760
線一條，我們可以看到，我們需要將超過

110
00:05:37,760 --> 00:05:39,530
列表中的每一個元素。

111
00:05:39,530 --> 00:05:42,150
除了最後一個元素中，由於第1族元素

112
00:05:42,150 --> 00:05:44,230
已排序的列表。

113
00:05:44,230 --> 00:05:48,100
線兩條，我們認為未排序的第一個元素

114
00:05:48,100 --> 00:05:51,080
部分的列表中是最低的，因為我們沒有與我們的

115
00:05:51,080 --> 00:05:53,750
例如，我們有一些比較。

116
00:05:53,750 --> 00:05:57,260
第三行開始第二個循環中，我們遍歷

117
00:05:57,260 --> 00:05:59,170
每一個未排序的元素。

118
00:05:59,170 --> 00:06:02,150
我們知道後，我迭代，排序的部分

119
00:06:02,150 --> 00:06:05,330
我們的名單必須有i個元素，因為每一步

120
00:06:05,330 --> 00:06:06,890
一種元素進行排序。

121
00:06:06,890 --> 00:06:11,770
因此，第一個未排序的元素必須是在位置i加1。

122
00:06:11,770 --> 00:06:15,440
第四行中，我們比較了當前元素的最低

123
00:06:15,440 --> 00:06:17,750
元素，我們已經看到了這麼遠。

124
00:06:17,750 --> 00:06:20,560
如果當前元素是小於最小

125
00:06:20,560 --> 00:06:23,870
元素，那麼我們記住當前的新元素

126
00:06:23,870 --> 00:06:26,250
最低線5。

127
00:06:26,250 --> 00:06:29,900
最後，在六，七行，我們交換最低

128
00:06:29,900 --> 00:06:33,080
元件與所述第一未排序的元件，從而

129
00:06:33,080 --> 00:06:36,990
將其添加到列表的排序部。

130
00:06:36,990 --> 00:06:40,030
一旦我們有一個算法，一個重要的問題要問

131
00:06:40,030 --> 00:06:43,370
自己作為程序員了多長時間？

132
00:06:43,370 --> 00:06:46,970
首先，我們會問這樣的問題如何需要多長時間，這

133
00:06:46,970 --> 00:06:50,070
在最壞的情況下運行的算法來？

134
00:06:50,070 --> 00:06:51,640
還記得我們代表這個運行

135
00:06:51,640 --> 00:06:55,060
大O符號的時間。

136
00:06:55,060 --> 00:06:58,650
為了確定最小的未分類的元素，

137
00:06:58,650 --> 00:07:01,880
基本上比較列表中的每個元素

138
00:07:01,880 --> 00:07:04,040
在列表中的所有其它元素。

139
00:07:04,040 --> 00:07:08,430
直觀地說，這聽起來像一個O n的平方操作。

140
00:07:08,430 --> 00:07:12,050
在我們的偽代碼，我們也有一個循環嵌套在

141
00:07:12,050 --> 00:07:14,420
另一個循環，這的確聽起來像一個O

142
00:07:14,420 --> 00:07:16,480
n的平方操作。

143
00:07:16,480 --> 00:07:19,250
但是，請記住，我們並不需要在

144
00:07:19,250 --> 00:07:23,460
整個列表時確定的最低未分類的元素嗎？

145
00:07:23,460 --> 00:07:26,600
一旦我們知道這4排序，例如，我們沒有

146
00:07:26,600 --> 00:07:28,170
需要再次來看待它。

147
00:07:28,170 --> 00:07:31,020
那麼，這降低了運行時間？

148
00:07:31,020 --> 00:07:34,510
在我們的名單長度為6，我們需要把五個

149
00:07:34,510 --> 00:07:37,990
比較的第一個元素，四個比較

150
00:07:37,990 --> 00:07:40,750
第二個元素，依此類推。

151
00:07:40,750 --> 00:07:44,690
這意味著，總的步數的總和

152
00:07:44,690 --> 00:07:49,160
從1到的列表的長度減1的整數。

153
00:07:49,160 --> 00:07:51,005
我們可以代表這一個總和。

154
00:07:57,980 --> 00:07:59,910
我們不會進入求和。

155
00:07:59,910 --> 00:08:04,900
但事實證明，這個總和是相等的n倍

156
00:08:04,900 --> 00:08:07,540
N減去2比1。

157
00:08:07,540 --> 00:08:14,220
或等價超過2，N的平方減去n超過2。

158
00:08:14,220 --> 00:08:18,860
在談到漸近運行，這n的平方項

159
00:08:18,860 --> 00:08:22,070
將主宰這n個任期。

160
00:08:22,070 --> 00:08:27,850
因此，選擇排序是O n的平方。

161
00:08:27,850 --> 00:08:31,460
回想一下，在我們的例子中，選擇排序仍然需要

162
00:08:31,460 --> 00:08:33,850
檢查一個數字，已經排序

163
00:08:33,850 --> 00:08:35,450
需要被感動。

164
00:08:35,450 --> 00:08:38,929
因此，這意味著，如果我們對一個已經跑了選擇排序

165
00:08:38,929 --> 00:08:43,070
排序的列表，這將需要相同數量的步驟，因為它

166
00:08:43,070 --> 00:08:46,340
將運行在一個完全未排序的列表。

167
00:08:46,340 --> 00:08:51,470
因此，選擇排序有最好的情況下表現為n的平方，

168
00:08:51,470 --> 00:08:56,820
我們所代表的與歐米茄Ň平方。

169
00:08:56,820 --> 00:08:58,600
這就是它的選擇排序。

170
00:08:58,600 --> 00:09:00,630
只是其中的的算法，我們可以

171
00:09:00,630 --> 00:09:02,390
使用對列表進行排序。

172
00:09:02,390 --> 00:09:05,910
我的名字是湯米，這是CS50。