[Powered by Google Translate] [冒泡排序]
[JACKSON施泰因坎普哈佛商学院]
[这是CS50。 CS50TV]
冒泡排序的排序算法是一个例子 -
也就是说，一个程序的一组中的元素进行排序
升序或降序排列。
例如，如果你想对数组进行排序的数字
[3，5，2，9]，冒泡排序的正确执行，将返回
排序的数组[2，3，5，9]以升序排列。
现在，我要解释的伪代码算法是如何工作的。
>> 比方说，我们在排序列表中的5个整数 - 3，2，9，6，5。
该算法开始通过在看的前两个元素，第3和2，
和检查，如果他们是彼此的相对顺序。
它们是 - 图3是大于2。
要在升序，他们应该是周围的其他方式。
因此，我们交换他们。
现在列表看起来像这样：[2，3，9，6，5]。
>> 接下来，我们来看看第二个和第三个，3个和9。
他们彼此相对正确的顺序。
也就是说，图3是小于9，所以该算法不交换它们。
接下来，我们来看看在9日和6。他们的订单。
>> 因此，我们需要更换，因为9大于6。
最后，我们来看看在过去的两个整数，9和5。
他们离开的命令，所以他们必须交换。
在列表中的第一个完整的通过，
它看起来是这样的：[2，3，6，5，9]。
不坏。这几乎排序。
但是，我们需要在列表中，再次得到完全排序。
二是小于3，所以我们不交换。
>> 三是小于6，所以我们不交换。
六是大于5。我们交换。
六是小于9。我们不交换。
第二次通过后，它看起来像这样：[2，3，5，6，9]。完美的。
现在，让我们把它写在伪代码。
基本上，对于列表中的每个元素，我们需要看
直接将其权利和元素。
如果它们是满分为了相对于彼此的 - 也就是说，如果在左边的元素
大于一个在右边 - 我们应该交换这两个元素。
>> 我们这样做的每一个元素的列表，我们已经取得了一个通过。
现在我们需要做的直通足够的时间，以确保清单
是充分，适当的排序。
但是，有多少次，我们必须通过列表
保证我们所做的吗？
好了，最坏的情况是，如果我们有一个完全向后列表。
然后，它需要一个数传递的数目等于
n-1个元素。
如果这样做没有意义的，直观的，想一个简单的例子 - 这样的名单[1]。
>> 这是要采取一个通到正确排序。
[3，2，1] - 最坏的情况是，3个元素排序向后，
这将需要2次迭代进行排序。
一次迭代后，[2，1，3]。
第二个投资收益率排序后的数组[1，2，3]。
所以，你知道，你从来没有去通过阵列，在一般情况，
超过n-1次，其中n是在数组中的元素数。
因为，这就是所谓的冒泡排序的最大元素趋向于“泡沫”
到很快的权利。
事实上，该算法具有非常有趣的现象。
>> 经过m次迭代整个数组，
最右边的m个元素是保证
到他们正确的位置进行排序。
如果你想看到这样的自己，
我们可以尝试在一个完全向后列表[9，6，5，3，2]。
后通过整个列表，
[声音写作]
[6，9，5，3，2]，[6，5，9，3，2]，[6，5，3，9，2]，[6，5，3，2，9]
最右边的元素是在适当的地方。
后的第二个直通，6将具有“鼓泡式'的
右数第二位。
这两个因素将在正确的地方正确的 - 第6和第9 -
经过前两道直通。
>> 那么，如何才能使用优化算法呢？
好了，一个迭代后，通过阵列
我们实际上并不需要检查一下最右边的元素
因为我们知道它的排序。
经过两次迭代，我们知道是肯定的，最右边的两个要素都到位。
所以，在一般情况下，通过充分阵列k次迭代后，
检查最后的k个元素是多余的，因为我们不知道
他们已经在正确的位置。
>> 因此，如果你的n个元素的数组排序，
在第一次迭代 - 你要排序的所有元素 - 第一n-0。
在第二次迭代中，你必须在所有的元素，但最后看 -
第一n-1。
另一种优化，以检查是否已排序的列表
在每次迭代之后。
如果它已经对数组进行排序，我们不需要做任何更多的迭代
通过列表。
如何才能做到这一点呢？
那么，如果我们不作任何掉期上一通通过的名单，
很明显，已经排序的列表，因为我们没有交换什么。
因此，我们绝对没有再次进行排序。
>> 也许你可以初始化一个标志变量，被称为“不排序”
false，然后将其更改为true，如果你要交换的任何元素
通过数组的一个迭代。
同样，一个计数器来计数多少掉期
在任何给定的迭代。
一个迭代结束时，如果你不交换任何元素，
你知道已排序的列表，你就大功告成了。
冒泡排序，像其他的排序算法，可以
调整，其中有一个排序方法中的任何元素。
>> 也就是说，给定两个元素，你有办法说，如果第一个
大于，等于或小于第二个。
例如，你可以说的字母排序
a <b的，B <C，等。
或者，你可以按星期几星期日是低于周一
这是小于星期二。
>> 冒泡排序绝不是一个非常有效的快速排序算法。
最坏情况下的运行是大O的n²
因为你有n次迭代通过列表
检查所有n个元素，每个传递的N×N = N²。
运行时间是指，作为你排序的元素数量增加，
运行时间的增加，二次。
>> 但是，如果效率是你的程序并不是一个大问题
或者，如果你只是少量的元素进行排序，
您可能会发现冒泡排序有用的，因为
它是一个最简单的排序算法，以了解
和代码。
这也是一个伟大的方式来获得经验与翻译理论
算法转换成实际的功能代码。
嗯，这是给你的冒泡排序。感谢收看。
CS50.TV