1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [冒泡排序]

2
00:00:02,840 --> 00:00:04,560
[JACKSON施泰因坎普哈佛商學院]

3
00:00:04,560 --> 00:00:07,500
[這是CS50。 CS50TV]

4
00:00:08,000 --> 00:00:11,730
冒泡排序的排序算法是一個例子 - 

5
00:00:11,730 --> 00:00:14,460
也就是說，一個程序的一組中的元素進行排序

6
00:00:14,460 --> 00:00:15,840
升序或降序排列。

7
00:00:15,840 --> 00:00:18,710
例如，如果你想對數組進行排序的數字

8
00:00:18,710 --> 00:00:23,060
[3，5，2，9]，冒泡排序的正確執行，將返回

9
00:00:23,060 --> 00:00:26,260
排序的數組[2，3，5，9]以升序排列。

10
00:00:26,260 --> 00:00:28,850
現在，我要解釋的偽代碼算法是如何工作的。

11
00:00:28,850 --> 00:00:34,000
>> 比方說，我們在排序列表中的5個整數 -  3，2，9，6，5。

12
00:00:34,000 --> 00:00:37,650
該算法開始通過在看的前兩個元素，第3和2，

13
00:00:37,650 --> 00:00:40,850
和檢查，如果他們是彼此的相對順序。

14
00:00:40,850 --> 00:00:43,150
它們是 - 圖3是大於2。

15
00:00:43,150 --> 00:00:45,190
要在升序，他們應該是周圍的其他方式。

16
00:00:45,190 --> 00:00:46,610
因此，我們交換他們。

17
00:00:46,610 --> 00:00:49,760
現在列表看起來像這樣：[2，3，9，6，5]。

18
00:00:49,760 --> 00:00:52,450
>> 接下來，我們來看看第二個和第三個，3個和9。

19
00:00:52,450 --> 00:00:55,770
他們彼此相對正確的順序。

20
00:00:55,770 --> 00:00:58,800
也就是說，圖3是小於9，所以該算法不交換它們。

21
00:00:58,800 --> 00:01:01,900
接下來，我們來看看在9日和6。他們的訂單。

22
00:01:01,900 --> 00:01:04,260
>> 因此，我們需要更換，因為9大於6。

23
00:01:04,260 --> 00:01:08,840
最後，我們來看看在過去的兩個整數，9和5。

24
00:01:08,840 --> 00:01:10,850
他們離開的命令，所以他們必須交換。

25
00:01:10,850 --> 00:01:13,360
在列表中的第一個完整的通過，

26
00:01:13,360 --> 00:01:17,140
它看起來是這樣的：[2，3，6，5，9]。

27
00:01:17,140 --> 00:01:19,690
不壞。這幾乎排序。

28
00:01:19,690 --> 00:01:22,450
但是，我們需要在列表中，再次得到完全排序。

29
00:01:22,450 --> 00:01:29,250
二是小於3，所以我們不交換。

30
00:01:29,250 --> 00:01:31,700
>> 三是小於6，所以我們不交換。

31
00:01:31,700 --> 00:01:35,500
六是大於5。我們交換。

32
00:01:35,500 --> 00:01:38,460
六是小於9。我們不交換。

33
00:01:38,460 --> 00:01:42,170
第二次通過後，它看起來像這樣：[2，3，5，6，9]。完美的。

34
00:01:42,170 --> 00:01:44,680
現在，讓我們把它寫在偽代碼。

35
00:01:44,680 --> 00:01:48,450
基本上，對於列表中的每個元素，我們需要看

36
00:01:48,450 --> 00:01:50,060
直接將其權利和元素。

37
00:01:50,060 --> 00:01:53,420
如果它們是滿分為了相對於彼此的 - 也就是說，如果在左邊的元素

38
00:01:53,420 --> 00:01:56,810
大於一個在右邊 - 我們應該交換這兩個元素。

39
00:01:56,810 --> 00:02:01,270
>> 我們這樣做的每一個元素的列表，我們已經取得了一個通過。

40
00:02:01,270 --> 00:02:05,160
現在我們需要做的直通足夠的時間，以確保清單

41
00:02:05,160 --> 00:02:06,480
是充分，適當的排序。

42
00:02:06,480 --> 00:02:08,889
但是，有多少次，我們必須通過列表

43
00:02:08,889 --> 00:02:10,400
保證我們所做的嗎？

44
00:02:10,400 --> 00:02:14,730
好了，最壞的情況是，如果我們有一個完全向後列表。

45
00:02:14,730 --> 00:02:17,840
然後，它需要一個數傳遞的數目等於

46
00:02:17,840 --> 00:02:19,730
n-1個元素。

47
00:02:19,730 --> 00:02:24,720
如果這樣做沒有意義的，直觀的，想一個簡單的例子 - 這樣的名單[1]。

48
00:02:24,720 --> 00:02:28,430
>> 這是要採取一個通到正確排序。

49
00:02:28,430 --> 00:02:33,060
[3，2，1]  - 最壞的情況是，3個元素排序向後，

50
00:02:33,060 --> 00:02:34,830
這將需要2次迭代進行排序。

51
00:02:34,830 --> 00:02:37,980
一次迭代後，[2，1，3]。

52
00:02:37,980 --> 00:02:39,550
第二個投資收益率排序後的數組[1，2，3]。

53
00:02:39,550 --> 00:02:43,350
所以，你知道，你從來沒有去通過陣列，在一般情況，

54
00:02:43,350 --> 00:02:46,790
超過n-1次，其中n是在數組中的元素數。

55
00:02:47,090 --> 00:02:50,470
因為，這就是所謂的冒泡排序的最大元素趨向於“泡沫”

56
00:02:50,470 --> 00:02:51,950
到很快的權利。

57
00:02:51,950 --> 00:02:53,980
事實上，該算法具有非常有趣的現象。

58
00:02:53,980 --> 00:02:57,410
>> 經過m次迭代整個數組，

59
00:02:57,410 --> 00:02:59,000
最右邊的m個元素是保證

60
00:02:59,000 --> 00:03:01,000
到他們正確的位置進行排序。

61
00:03:01,000 --> 00:03:02,280
如果你想看到這樣的自己，

62
00:03:02,280 --> 00:03:05,500
我們可以嘗試在一個完全向後列表[9，6，5，3，2]。

63
00:03:05,500 --> 00:03:08,220
後通過整個列表，

64
00:03:08,220 --> 00:03:09,220
[聲音寫作]

65
00:03:09,220 --> 00:03:18,790
[6，9，5，3，2]，[6，5，9，3，2]，[6，5，3，9，2]，[6，5，3，2，9]

66
00:03:18,790 --> 00:03:21,250
最右邊的元素是在適當的地方。

67
00:03:21,250 --> 00:03:24,760
後的第二個直通，6將具有“鼓泡式'的

68
00:03:24,760 --> 00:03:26,220
右數第二位。

69
00:03:26,220 --> 00:03:28,840
這兩個因素將在正確的地方正確的 - 第6和第9  - 

70
00:03:28,840 --> 00:03:30,580
經過前兩道直通。

71
00:03:30,580 --> 00:03:32,590
>> 那麼，如何才能使用優化算法呢？

72
00:03:32,590 --> 00:03:34,850
好了，一個迭代後，通過陣列

73
00:03:34,850 --> 00:03:37,690
我們實際上並不需要檢查一下最右邊的元素

74
00:03:37,690 --> 00:03:39,200
因為我們知道它的排序。

75
00:03:39,200 --> 00:03:43,050
經過兩次迭代，我們知道是肯定的，最右邊的兩個要素都到位。

76
00:03:43,050 --> 00:03:48,260
所以，在一般情況下，通過充分陣列k次迭代後，

77
00:03:48,260 --> 00:03:51,550
檢查最後的k個元素是多餘的，因為我們不知道

78
00:03:51,550 --> 00:03:52,360
他們已經在正確的位置。

79
00:03:52,360 --> 00:03:54,870
>> 因此，如果你的n個元素的數組排序，

80
00:03:54,870 --> 00:03:57,870
在第一次迭代 - 你要排序的所有元素 - 第一n-0。

81
00:03:57,870 --> 00:04:04,170
在第二次迭代中，你必須在所有的元素，但最後看 - 

82
00:04:04,170 --> 00:04:07,090
第一n-1。

83
00:04:07,090 --> 00:04:10,520
另一種優化，以檢查是否已排序的列表

84
00:04:10,520 --> 00:04:11,710
在每次迭代之後。

85
00:04:11,710 --> 00:04:13,900
如果它已經對數組進行排序，我們不需要做任何更多的迭代

86
00:04:13,900 --> 00:04:15,310
通過列表。

87
00:04:15,310 --> 00:04:16,220
如何才能做到這一點呢？

88
00:04:16,220 --> 00:04:19,360
那麼，如果我們不作任何掉期上一通通過的名單，

89
00:04:19,360 --> 00:04:22,350
很明顯，已經排序的列表，因為我們沒有交換什麼。

90
00:04:22,350 --> 00:04:24,160
因此，我們絕對沒有再次進行排序。

91
00:04:24,160 --> 00:04:27,960
>> 也許你可以初始化一個標誌變量，被稱為“不排序”

92
00:04:27,960 --> 00:04:30,990
false，然後將其更改為true，如果你要交換的任何元素

93
00:04:30,990 --> 00:04:32,290
通過數組的一個迭代。

94
00:04:32,290 --> 00:04:35,350
同樣，一個計數器來計數多少掉期

95
00:04:35,350 --> 00:04:37,040
在任何給定的迭代。

96
00:04:37,040 --> 00:04:40,040
一個迭代結束時，如果你不交換任何元素，

97
00:04:40,040 --> 00:04:41,780
你知道已排序的列表，你就大功告成了。

98
00:04:41,780 --> 00:04:44,090
冒泡排序，像其他的排序算法，可以

99
00:04:44,090 --> 00:04:46,960
調整，其中有一個排序方法中的任何元素。

100
00:04:46,960 --> 00:04:50,610
>> 也就是說，給定兩個元素，你有辦法說，如果第一個

101
00:04:50,610 --> 00:04:53,770
大於，等於或小於第二個。

102
00:04:53,770 --> 00:04:56,870
例如，你可以說的字母排序

103
00:04:56,870 --> 00:05:00,520
a <b的，B <C，等。

104
00:05:00,520 --> 00:05:03,830
或者，你可以按星期幾星期日是低於週一

105
00:05:03,830 --> 00:05:05,110
這是小於星期二。

106
00:05:05,110 --> 00:05:09,630
>> 冒泡排序絕不是一個非常有效的快速排序算法。

107
00:05:09,630 --> 00:05:12,370
最壞情況下的運行是大O的n²

108
00:05:12,370 --> 00:05:14,810
因為你有n次迭代通過列表

109
00:05:14,810 --> 00:05:18,430
檢查所有n個元素，每個傳遞的N×N = N²。

110
00:05:18,430 --> 00:05:22,730
運行時間是指，作為你排序的元素數量增加，

111
00:05:22,730 --> 00:05:24,330
運行時間的增加，二次。

112
00:05:24,330 --> 00:05:27,330
>> 但是，如果效率是你的程序並不是一個大問題

113
00:05:27,330 --> 00:05:29,550
或者，如果你只是少量的元素進行排序，

114
00:05:29,550 --> 00:05:31,660
您可能會發現冒泡排序有用的，因為

115
00:05:31,660 --> 00:05:33,360
它是一個最簡單的排序算法，以了解

116
00:05:33,360 --> 00:05:34,250
和代碼。

117
00:05:34,250 --> 00:05:37,270
這也是一個偉大的方式來獲得經驗與翻譯理論

118
00:05:37,270 --> 00:05:40,220
算法轉換成實際的功能代碼。

119
00:05:40,220 --> 00:05:43,000
嗯，這是給你的冒泡排序。感謝收看。

120
00:05:43,000 --> 00:05:44,000
CS50.TV