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