>> [音乐播放]
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。