[音乐播放] DOUG LLOYD：好吧，所以 冒泡排序是一种算法 你可以用它来进行排序一组元素。 让我们来看看它是如何工作的。 

这样的基本思想后面 冒泡排序是这样的。 我们一般要走高 值元素通常到右侧， 和一般较低值元素 到左侧，如我们所期望的。 我们要下的东西是在 开始时，具有较高的事 是在末端。 

我们是如何做到这一点？ 那么在伪代码， 我们可以说，我们的 设置一个交换计数器为非零值。 我们将看到，为什么我们这样做，在第二。 随后，我们重复以下 过程，直到交换计数为0， 或者直到我们不掉的。 

重置互换计数器 0，如果它不是已经0。 然后看每 相邻的一对元件。 如果这两个因素是 不是为了，交换它们， 加1到交换柜台。 如果你正在考虑 这个你想象它之前， 注意到，这将移动下 值元素向左 和更高的值元素到右侧， 有效地做我们想做的事情， 这是将这些团体 在该方式的元件。 让我们直观地了解本 看起来使用我们的数组 我们用来测试 这些算法。 我们有一个排序的数组在这里再次， 通过所有的元素表示 是红色。 我把我交换反 为非零值。 我随意选择 负1--这不是0。 我们想重复这个过程 直到交换计数器为0。 这就是为什么我把我交换 计数器到一些非零值， 因为否则 交换计数器将是0。 我们甚至不会开始 算法的过程。 如此反复，步骤are-- 复位交换计数器 为0，再看看每个相邻 对，如果他们不按顺序， 交换它们，并添加1 到交换柜台。 因此，让我们开始这个过程。 所以我们要做的第一件事就是 我们设置交换计数器为0， 然后我们开始寻找 在每个相邻的一对。 

所以，我们首先开始看5和2。 我们看到，他们是出 订货所以我们交换它们。 我们增加1到交换柜台。 所以，现在我们交换计数器1， 和2和5已经被切换。 现在，我们再次重复这个过程。 

我们期待下一个相邻的一对， 5 1--他们也失灵， 所以我们交换他们并添加 1到交换柜台。 然后我们来看看5和3。 他们是失灵的，所以我们交换 他们和我们添加1到交换柜台。 然后我们来看看5和6。 他们是为了，所以我们实际上并不 这需要时间来交换任何东西。 然后我们来看看6和4。 他们还坏了，所以我们交换 他们和我们添加1到交换柜台。 

现在可以看到发生了什么事。 我们已经搬到6一直到结束。 因此，在选择排序，如果你 看到视频，我们所做的是 我们结束了移动 建筑最小元素 数组排序基本上是从 从左到右，最小到最大。 在冒泡排序的情况下，如果我们 下面这个特殊的算法， 我们实际上将要建设 从右侧的排序的数组 到左，从最大到最小。 我们已经有效地冒泡6， 最大值，一直到结束。 

因此，我们现在可以宣布 这是排序， 和未来iterations-- 经过阵列again-- 我们不必考虑6了。 我们只需要考虑 未排序的元素 当我们正在寻找相邻的一对。 因此，我们已完成一个 通过冒泡排序。 所以，现在我们回到正题， 重复，直到交换计数器为0。 那么交换计数器 是4，所以我们要 保持再重复这个过程。 

我们要重新交换计数器 为0，并期待在各相邻对。 因此，我们开始与2 1--他们 坏了，所以我们交换他们 我们增加1到交换柜台。 2和3，他们在秩序。 我们不需要做任何事情。 3和5是在顺序。 我们不需要做任何事情在那里。 

5和4，它们是从 秩序，因此我们 需要调换并添加 1到交换柜台。 而现在我们已经搬到5， 下一个最大的元素， 到未排序部分的端部。 所以，我们现在可以称之为 排序部的一部分。 

现在你在看 屏幕大概可以告诉， 因为我可以，该阵列 排序现在。 但是，我们不能证明呢。 我们没有担保 ，它的排序。 但是，这是交换 计数器将开始发挥作用。 

因此，我们已经完成了一通。 交换计数器2。 所以，我们要重复 这一过程中再次， 重复，直到交换计数器为0。 重置互换计数器为0。 因此，我们将重新设置。 

现在看每一对相邻。 这是为了，1和2。 2和3是为了。 3和4是为了。 所以在这一点上，注意到我们已经完成 看着每对相邻， 但交换柜台仍是0。 

如果我们没有切换 的任何元件，则它们 必须按顺序，由 凭借这个过程。 于是各种各样的效率， 我们的计算机科学家喜欢， 是我们现在可以宣布 整个数组必须 进行排序，因为我们没有 要交换的任何元素。 这是相当不错的。 

那么什么是最坏的情况下 场景与冒泡排序？ 在最坏的情况下，阵列是 在完全相反的顺序， 所以我们要泡每个 大元素的所有 跨越阵列的方式。 我们有效地也有 泡泡所有的小元素后面 在阵列一路，太。 因此，每个n个元件具有移动 在所有其他的n个元素。 所以这是最坏的情况。 在最好的情况下， 场景虽然，这是 略有不同的选择排序。 该阵列是已经 排序，当我们进去的。 我们没有做任何 掉期交易在第一轮。 所以，我们不妨来看看 在较少的元素，对不对？ 我们并不需要重复此 过处理的次数。 

那么，是什么意思呢？ 那么什么是最坏的情况下 对于冒泡排序，这有什么 在最好的情况下进行冒泡排序？ 你猜呢？ 在最坏的情况下，你必须遍历 在所有的n个元素n次。 因此，最坏的情况下为n的平方。 

如果数组是完全 虽然排序，你只 来看看每个 的一次的元素。 并且如果交换计数器仍为0， 你可以说这个数组排序。 因此在最好的情况下，这是 实际上比选择好 类别 - 这是为n的欧米茄。 

我是道格·劳埃德。 这是CS50。