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