>> [音乐播放]
道格·劳埃德：选择排序是 算法，正如您所料，
排序一组元素。
与算法召回 是一步一步的设置
的用于完成任务的指令。
>> 在选择排序 基本思路是这样，
找到最小的未分类的元素， 其添加到排序的列表的末尾。
有效地这样做是什么版本 排序列表，一次一个元件。
将它分解为伪 我们可以说明这个算法
如下所示，重复上述操作直至 没有排序的元素依然存在。
通过搜索未排序 数据，以找到最小的值，
然后交换的最小值与 未排序的部分的第一要素。
>> 它可以帮助想象这一点， 让我们来看看这个。
所以，我主张，是一个 排序的数组，我已经
通过表明所有表示，它 元素为红色，
它们还未排序。
这是整个 阵列的未分类的一部分。
>> 因此，让我们通过以下步骤： 选择排序该数组进行排序。
所以，再一次，我们要重复 直到没有未分类的元素依然存在。
我们通过要去搜索 数据，以找到最小的值，
然后交换用该值 未排序的部分的第一要素。
>> 现在，再次，整个 数组是未排序的一部分。
所有的红色元素是无序。
所以我们通过搜索和 我们发现的最小值。
我们从头开始， 我们去年底，
我们发现最小的值，之一。
所以这是第一部分。
然后第二部分，换用该值 未排序部分的第一要素，
还是先红素。
>> 在这种情况下，这将是 五，所以我们换一到五。
当我们做到这一点，我们就可以 直观地看到，我们已经
移动最小的值元素 阵列的，到最开始。
有效地排序的元素。
>> 因此，我们的确可以确认 并指出之一，排序。
因此，我们将指示排序部分 我们的阵列，通过着色它的蓝色。
>> 现在，我们只需再次重复这个过程。
我们通过对未分类的部分搜索 阵列找到的最小元素。
在这种情况下，它的两种。
>> 我们交换与第一 未排序的部分元素。
在这种情况下，双方还恰好是 未排序部分的第一个元素。
因此，我们交换两个与自身， 这真的只是留下了两个
它在哪里，并且它的排序。
继续，我们通过搜索 找到的最小元素。
这三种。
我们的第一个交换是 元素，这是五。
现在，三是排序。
>> 我们通过再次搜索，而我们 找到最小的元素为四。
我们用的第一个元素将其交换 未分类的一部分，现在四是排序。
>> 我们发现，五是 的最小元素。
我们的第一个交换是 未排序的部分元素。
而现在五是排序。
>> 然后最后，我们 未分类的部分由
只是一个单一的元件的， 所以我们通过搜索
而且我们发现六是 最小的，而事实上，唯一的元素。
然后，我们可以说，它是排序。
而现在，我们已经关掉我们的数组 被完全未排序
红色，完全排序 蓝色，使用选择排序。
>> 那么什么是最糟糕的情况吗？
那么在绝对最差 情况下，我们必须过目
所有的数组的元素的 找到最小的未分类的元素，
我们要重复 这个过程n次。
一旦对阵列的每个元素 因为我们只在这个算法中，
在时间排序一个元素。
>> 什么是最好的情况？
那么它是完全一样的，对不对？
实际上，我们必须通过仍然步骤 该阵列的每一个元素
为了确认它， 事实上，最小的元素。
>> 因此，最坏的情况下运行时，我们 要重复一个过程n次，
一次，每个n个元素。
并且在最好的情况下， 我们必须这样做。
>> 所以，回想起我们 计算复杂性的工具箱，
你觉得是最糟糕的 情况下运行时选择排序？
你认为什么是最好的 情况下运行时选择排序？
>> 你猜大O n个平方， 和N大欧米茄平方？
你是对的。
那些是，事实上，该 最坏的情况下，最好的情况下运行
次，选择排序。
>> 我是道格·劳埃德。
这是CS50。