1
00:00:00,000 --> 00:00:03,360
>> [音樂播放]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD：好吧，所以
冒泡排序是一種算法

4
00:00:06,730 --> 00:00:08,730
你可以用它來進行排序一組元素。

5
00:00:08,730 --> 00:00:10,850
讓我們來看看它是如何工作的。

6
00:00:10,850 --> 00:00:13,240
>> 這樣的基本思想後面
冒泡排序是這樣的。

7
00:00:13,240 --> 00:00:17,340
我們一般要走高
值元素通常到右側，

8
00:00:17,340 --> 00:00:20,340
和一般較低值元素
到左側，如我們所期望的。

9
00:00:20,340 --> 00:00:23,256
我們要下的東西是在
開始時，具有較高的事

10
00:00:23,256 --> 00:00:24,970
是在末端。

11
00:00:24,970 --> 00:00:26,130
>> 我們是如何做到這一點？

12
00:00:26,130 --> 00:00:28,040
那麼在偽代碼，
我們可以說，我們的

13
00:00:28,040 --> 00:00:30,320
設置一個交換計數器為非零值。

14
00:00:30,320 --> 00:00:32,570
我們將看到，為什麼我們這樣做，在第二。

15
00:00:32,570 --> 00:00:36,090
隨後，我們重複以下
過程，直到交換計數為0，

16
00:00:36,090 --> 00:00:39,910
或者直到我們不掉的。

17
00:00:39,910 --> 00:00:43,170
>> 重置互換計數器
0，如果它不是已經0。

18
00:00:43,170 --> 00:00:46,420
然後看每
相鄰的一對元件。

19
00:00:46,420 --> 00:00:49,550
如果這兩個因素是
不是為了，交換它們，

20
00:00:49,550 --> 00:00:51,620
加1到交換櫃檯。

21
00:00:51,620 --> 00:00:53,870
如果你正在考慮
這個你想像它之前，

22
00:00:53,870 --> 00:00:57,471
注意到，這將移動下
值元素向左

23
00:00:57,471 --> 00:01:00,720
和更高的值元素到右側，
有效地做我們想做的事情，

24
00:01:00,720 --> 00:01:03,940
這是將這些團體
在該方式的元件。

25
00:01:03,940 --> 00:01:07,035
讓我們直觀地了解本
看起來使用我們的數組

26
00:01:07,035 --> 00:01:10,504
我們用來測試
這些算法。

27
00:01:10,504 --> 00:01:13,420
我們有一個排序的數組在這裡再次，
通過所有的元素表示

28
00:01:13,420 --> 00:01:14,840
是紅色。

29
00:01:14,840 --> 00:01:17,970
我把我交換反
為非零值。

30
00:01:17,970 --> 00:01:20,610
我隨意選擇
負1--這不是0。

31
00:01:20,610 --> 00:01:23,840
我們想重複這個過程
直到交換計數器為0。

32
00:01:23,840 --> 00:01:26,540
這就是為什麼我把我交換
計數器到一些非零值，

33
00:01:26,540 --> 00:01:29,400
因為否則
交換計數器將是0。

34
00:01:29,400 --> 00:01:31,610
我們甚至不會開始
算法的過程。

35
00:01:31,610 --> 00:01:33,610
如此反复，步驟are--
復位交換計數器

36
00:01:33,610 --> 00:01:37,900
為0，再看看每個相鄰
對，如果他們不按順序，

37
00:01:37,900 --> 00:01:40,514
交換它們，並添加1
到交換櫃檯。

38
00:01:40,514 --> 00:01:41,680
因此，讓我們開始這個過程。

39
00:01:41,680 --> 00:01:44,430
所以我們要做的第一件事就是
我們設置交換計數器為0，

40
00:01:44,430 --> 00:01:46,660
然後我們開始尋找
在每個相鄰的一對。

41
00:01:46,660 --> 00:01:49,140
>> 所以，我們首先開始看5和2。

42
00:01:49,140 --> 00:01:52,410
我們看到，他們是出
訂貨所以我們交換它們。

43
00:01:52,410 --> 00:01:53,830
我們增加1到交換櫃檯。

44
00:01:53,830 --> 00:01:57,860
所以，現在我們交換計數器1，
和2和5已經被切換。

45
00:01:57,860 --> 00:01:59,370
現在，我們再次重複這個過程。

46
00:01:59,370 --> 00:02:03,540
>> 我們期待下一個相鄰的一對，
5 1--他們也失靈，

47
00:02:03,540 --> 00:02:06,960
所以我們交換他們並添加
1到交換櫃檯。

48
00:02:06,960 --> 00:02:08,900
然後我們來看看5和3。

49
00:02:08,900 --> 00:02:13,830
他們是失靈的，所以我們交換
他們和我們添加1到交換櫃檯。

50
00:02:13,830 --> 00:02:15,550
然後我們來看看5和6。

51
00:02:15,550 --> 00:02:18,630
他們是為了，所以我們實際上並不
這需要時間來交換任何東西。

52
00:02:18,630 --> 00:02:20,250
然後我們來看看6和4。

53
00:02:20,250 --> 00:02:24,920
他們還壞了，所以我們交換
他們和我們添加1到交換櫃檯。

54
00:02:24,920 --> 00:02:26,230
>> 現在可以看到發生了什麼事。

55
00:02:26,230 --> 00:02:29,514
我們已經搬到6一直到結束。

56
00:02:29,514 --> 00:02:32,180
因此，在選擇排序，如果你
看到視頻，我們所做的是

57
00:02:32,180 --> 00:02:35,290
我們結束了移動
建築最小元素

58
00:02:35,290 --> 00:02:39,640
數組排序基本上是從
從左到右，最小到最大。

59
00:02:39,640 --> 00:02:43,200
在冒泡排序的情況下，如果我們
下面這個特殊的算法，

60
00:02:43,200 --> 00:02:46,720
我們實際上將要建設
從右側的排序的數組

61
00:02:46,720 --> 00:02:49,100
到左，從最大到最小。

62
00:02:49,100 --> 00:02:53,840
我們已經有效地冒泡6，
最大值，一直到結束。

63
00:02:53,840 --> 00:02:56,165
>> 因此，我們現在可以宣布
這是排序，

64
00:02:56,165 --> 00:02:59,130
和未來iterations--
經過陣列again--

65
00:02:59,130 --> 00:03:01,280
我們不必考慮6了。

66
00:03:01,280 --> 00:03:03,850
我們只需要考慮
未排序的元素

67
00:03:03,850 --> 00:03:06,299
當我們正在尋找相鄰的一對。

68
00:03:06,299 --> 00:03:08,340
因此，我們已完成一個
通過冒泡排序。

69
00:03:08,340 --> 00:03:11,941
所以，現在我們回到正題，
重複，直到交換計數器為0。

70
00:03:11,941 --> 00:03:13,690
那麼交換計數器
是4，所以我們要

71
00:03:13,690 --> 00:03:15,410
保持再重複這個過程。

72
00:03:15,410 --> 00:03:19,180
>> 我們要重新交換計數器
為0，並期待在各相鄰對。

73
00:03:19,180 --> 00:03:21,890
因此，我們開始與2 1--他們
壞了，所以我們交換他們

74
00:03:21,890 --> 00:03:23,620
我們增加1到交換櫃檯。

75
00:03:23,620 --> 00:03:25,490
2和3，他們在秩序。

76
00:03:25,490 --> 00:03:27,060
我們不需要做任何事情。

77
00:03:27,060 --> 00:03:28,420
3和5是在順序。

78
00:03:28,420 --> 00:03:30,150
我們不需要做任何事情在那裡。

79
00:03:30,150 --> 00:03:32,515
>> 5和4，它們是從
秩序，因此我們

80
00:03:32,515 --> 00:03:35,130
需要調換並添加
1到交換櫃檯。

81
00:03:35,130 --> 00:03:38,880
而現在我們已經搬到5，
下一個最大的元素，

82
00:03:38,880 --> 00:03:40,920
到未排序部分的端部。

83
00:03:40,920 --> 00:03:44,360
所以，我們現在可以稱之為
排序部的一部分。

84
00:03:44,360 --> 00:03:47,180
>> 現在你在看
屏幕大概可以告訴，

85
00:03:47,180 --> 00:03:50,130
因為我可以，該陣列
排序現在。

86
00:03:50,130 --> 00:03:51,820
但是，我們不能證明呢。

87
00:03:51,820 --> 00:03:54,359
我們沒有擔保
，它的排序。

88
00:03:54,359 --> 00:03:56,900
但是，這是交換
計數器將開始發揮作用。

89
00:03:56,900 --> 00:03:59,060
>> 因此，我們已經完成了一通。

90
00:03:59,060 --> 00:04:00,357
交換計數器2。

91
00:04:00,357 --> 00:04:02,190
所以，我們要重複
這一過程中再次，

92
00:04:02,190 --> 00:04:04,290
重複，直到交換計數器為0。

93
00:04:04,290 --> 00:04:05,550
重置互換計數器為0。

94
00:04:05,550 --> 00:04:06,820
因此，我們將重新設置。

95
00:04:06,820 --> 00:04:09,810
>> 現在看每一對相鄰。

96
00:04:09,810 --> 00:04:11,880
這是為了，1和2。

97
00:04:11,880 --> 00:04:13,590
2和3是為了。

98
00:04:13,590 --> 00:04:15,010
3和4是為了。

99
00:04:15,010 --> 00:04:19,250
所以在這一點上，注意到我們已經完成
看著每對相鄰，

100
00:04:19,250 --> 00:04:22,530
但交換櫃檯仍是0。

101
00:04:22,530 --> 00:04:25,520
>> 如果我們沒有切換
的任何元件，則它們

102
00:04:25,520 --> 00:04:28,340
必須按順序，由
憑藉這個過程。

103
00:04:28,340 --> 00:04:32,000
於是各種各樣的效率，
我們的計算機科學家喜歡，

104
00:04:32,000 --> 00:04:35,560
是我們現在可以宣布
整個數組必須

105
00:04:35,560 --> 00:04:38,160
進行排序，因為我們沒有
要交換的任何元素。

106
00:04:38,160 --> 00:04:40,380
這是相當不錯的。

107
00:04:40,380 --> 00:04:43,260
>> 那麼什麼是最壞的情況下
場景與冒泡排序？

108
00:04:43,260 --> 00:04:46,240
在最壞的情況下，陣列是
在完全相反的順序，

109
00:04:46,240 --> 00:04:49,870
所以我們要泡每個
大元素的所有

110
00:04:49,870 --> 00:04:51,780
跨越陣列的方式。

111
00:04:51,780 --> 00:04:55,350
我們有效地也有
泡泡所有的小元素後面

112
00:04:55,350 --> 00:04:57,050
在陣列一路，太。

113
00:04:57,050 --> 00:05:01,950
因此，每個n個元件具有移動
在所有其他的n個元素。

114
00:05:01,950 --> 00:05:04,102
所以這是最壞的情況。

115
00:05:04,102 --> 00:05:05,810
在最好的情況下，
場景雖然，這是

116
00:05:05,810 --> 00:05:07,880
略有不同的選擇排序。

117
00:05:07,880 --> 00:05:10,040
該陣列是已經
排序，當我們進去的。

118
00:05:10,040 --> 00:05:12,550
我們沒有做任何
掉期交易在第一輪。

119
00:05:12,550 --> 00:05:14,940
所以，我們不妨來看看
在較少的元素，對不對？

120
00:05:14,940 --> 00:05:18,580
我們並不需要重複此
過處理的次數。

121
00:05:18,580 --> 00:05:19,540
>> 那麼，是什麼意思呢？

122
00:05:19,540 --> 00:05:22,390
那麼什麼是最壞的情況下
對於冒泡排序，這有什麼

123
00:05:22,390 --> 00:05:25,330
在最好的情況下進行冒泡排序？

124
00:05:25,330 --> 00:05:27,770
你猜呢？

125
00:05:27,770 --> 00:05:32,420
在最壞的情況下，你必須遍歷
在所有的n個元素n次。

126
00:05:32,420 --> 00:05:34,220
因此，最壞的情況下為n的平方。

127
00:05:34,220 --> 00:05:36,550
>> 如果數組是完全
雖然排序，你只

128
00:05:36,550 --> 00:05:38,580
來看看每個
的一次的元素。

129
00:05:38,580 --> 00:05:42,670
並且如果交換計數器仍為0，
你可以說這個數組排序。

130
00:05:42,670 --> 00:05:45,780
因此在最好的情況下，這是
實際上比選擇好

131
00:05:45,780 --> 00:05:49,230
類別 - 這是為n的歐米茄。

132
00:05:49,230 --> 00:05:50,270
>> 我是道格·勞埃德。

133
00:05:50,270 --> 00:05:52,140
這是CS50。

134
00:05:52,140 --> 00:05:54,382