[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