[音乐播放] 道格·劳埃德：选择排序是 算法，正如您所料， 排序一组元素。 与算法召回 是一步一步的设置 的用于完成任务的指令。 

在选择排序 基本思路是这样， 找到最小的未分类的元素， 其添加到排序的列表的末尾。 有效地这样做是什么版本 排序列表，一次一个元件。 将它分解为伪 我们可以说明这个算法 如下所示，重复上述操作直至 没有排序的元素依然存在。 通过搜索未排序 数据，以找到最小的值， 然后交换的最小值与 未排序的部分的第一要素。 

它可以帮助想象这一点， 让我们来看看这个。 所以，我主张，是一个 排序的数组，我已经 通过表明所有表示，它 元素为红色， 它们还未排序。 这是整个 阵列的未分类的一部分。 

因此，让我们通过以下步骤： 选择排序该数组进行排序。 所以，再一次，我们要重复 直到没有未分类的元素依然存在。 我们通过要去搜索 数据，以找到最小的值， 然后交换用该值 未排序的部分的第一要素。 

现在，再次，整个 数组是未排序的一部分。 所有的红色元素是无序。 所以我们通过搜索和 我们发现的最小值。 我们从头开始， 我们去年底， 我们发现最小的值，之一。 所以这是第一部分。 然后第二部分，换用该值 未排序部分的第一要素， 还是先红素。 

在这种情况下，这将是 五，所以我们换一到五。 当我们做到这一点，我们就可以 直观地看到，我们已经 移动最小的值元素 阵列的，到最开始。 有效地排序的元素。 

因此，我们的确可以确认 并指出之一，排序。 因此，我们将指示排序部分 我们的阵列，通过着色它的蓝色。 

现在，我们只需再次重复这个过程。 我们通过对未分类的部分搜索 阵列找到的最小元素。 在这种情况下，它的两种。 

我们交换与第一 未排序的部分元素。 在这种情况下，双方还恰好是 未排序部分的第一个元素。 因此，我们交换两个与自身， 这真的只是留下了两个 它在哪里，并且它的排序。 继续，我们通过搜索 找到的最小元素。 这三种。 我们的第一个交换是 元素，这是五。 现在，三是排序。 

我们通过再次搜索，而我们 找到最小的元素为四。 我们用的第一个元素将其交换 未分类的一部分，现在四是排序。 

我们发现，五是 的最小元素。 我们的第一个交换是 未排序的部分元素。 而现在五是排序。 

然后最后，我们 未分类的部分由 只是一个单一的元件的， 所以我们通过搜索 而且我们发现六是 最小的，而事实上，唯一的元素。 然后，我们可以说，它是排序。 而现在，我们已经关掉我们的数组 被完全未排序 红色，完全排序 蓝色，使用选择排序。 

那么什么是最糟糕的情况吗？ 那么在绝对最差 情况下，我们必须过目 所有的数组的元素的 找到最小的未分类的元素， 我们要重复 这个过程n次。 一旦对阵列的每个元素 因为我们只在这个算法中， 在时间排序一个元素。 

什么是最好的情况？ 那么它是完全一样的，对不对？ 实际上，我们必须通过仍然步骤 该阵列的每一个元素 为了确认它， 事实上，最小的元素。 

因此，最坏的情况下运行时，我们 要重复一个过程n次， 一次，每个n个元素。 并且在最好的情况下， 我们必须这样做。 

所以，回想起我们 计算复杂性的工具箱， 你觉得是最糟糕的 情况下运行时选择排序？ 你认为什么是最好的 情况下运行时选择排序？ 

你猜大O n个平方， 和N大欧米茄平方？ 你是对的。 那些是，事实上，该 最坏的情况下，最好的情况下运行 次，选择排序。 

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