[Powered by Google Translate] TOMMY:让我们来看看在选择排序的算法 的号码列表和排序。 一种算法,记住,是一个简单的一步一步的 完成任务的过程。 选择排序的基本理念是将 我们的名单分为两部分 - 一个的排序部分和未排序的部分。 该算法在每个步骤中,一个数字移动从 直到最后的排序条件部分的未分类的部分 整个列表进行排序。 所以这里有一个列表中的六个数字 - 23,42,4,16,8,和15。 现在被认为是整个列表排序。 即使16这样的数字可能已经在其正确的 位置,我们的算法有没有办法知道,直到 整个列表进行排序。 因此,我们会考虑每一个数字无序的,直到我们整理 它自己。 我们知道,我们要以升序排列的列表。 因此,我们将要建立我们的名单的排序部分 由左到右,从最小到最大。 要做到这一点,我们需要找到最小的未分类的元素 并把它在排序的部分结束。 由于此列表未排序,只有这样,才能做到这一点是 看在未排序的部分,记忆中的每个元素 哪一个元素是最低的和比较 每个元素。 因此,我们将首先在23。 这是我们所见过的第一个元素,所以我们会记住 它作为最低。 接下来,我们看42。 42是大于23,所以23仍然是最低。 其次是4,这是小于23,所以我们会记住4 作为新的最小值。 接下来是16,这是大于4,所以4 仍然是最低。 图8是大于4,和图15是大于4,所以4必须是 最小的未分类的元素。 因此,即使作为人类,我们可以立即看到,4 最小的元素,我们的算法需要看 每一个未排序的元素,即使我们已经找到了4 - 最小的元素。 所以,现在,我们已经发现的最小元素,4,我们将要 将它移动到列表的排序部。 由于这是第一个步骤中,这意味着我们希望把4日 在列表的开头。 现在图23是在列表的开头,所以 让我们交换的4个和23个。 所以,现在我们的名单看起来是这样的。 我们知道,4必须是在其最终位置,因为它是 两个最小的元素和元素的开头 的列表。 因此,这意味着,我们永远不需要再次移动它。 因此,让我们重复此过程,添加另一个元素 排序的列表中的部分。 我们知道,我们并不需要,因为它是在4 已经排序。 因此,我们就可以开始的42个,我们会记住的 最小的元素。 所以接下来我们来看看23小于42,所以我们 记得23是新的最低。 接下来,我们看到这是小于23的16,所以 16是新的最低。 现在我们来看看在8小于16,所以 图8是新的最小值。 和最后8是小于15,因此,我们知道,图8是一个最小 未分类的元素。 因此,这意味着我们应该附加的排序 列表中的部分。 现在是唯一的排序元素,所以我们想要把 接下来的8到4。 由于42是第一要素,在未排序的部分 名单中,我们将要交换42和8。 所以,现在我们的名单看起来是这样的。 图4和图8表示排序的列表中的部分,并 剩下的数字表示未分类的 列表中的部分。 因此,让我们继续进行下一次迭代。 我们从23日的时间,因为我们不需要看 在4和8了,因为他们已经 已排序。 16小于23,所以我们会记住 16作为新的最小值。 图16是小于42,但图15是小于16,所以15必须是 最低未分类的元素。 所以,现在我们要交换15日和23日至 在此给我们的清单。 已排序的列表中的部分由4,8和15,以及 这些元素依然排序。 但它只是恰巧下一个未排序的元素,16, 已经排序。 然而,有没有办法知道我们的算法,16 已经在正确的位置,所以我们仍然需要 重复完全相同的相同的过程。 所以我们看到,图16是小于42,和图16是小于23,所以 16必须的最小元素。 交换这个元素本身,这是不可能的,所以我们可以 简单地离开这个位置。 因此,我们需要一个更通过我们的算法。 图42是大于23,所以23必须是 最低未分类的元素。 一旦我们交换23和42,我们结束了我们的最终 排序的列表 - 4,8,15,16,23,42。 我们知道42必须在正确的地方,因为它是 唯一的元素离开,这就是选择排序。 现在让我们来规范我们的算法与一些 伪代码。 线一条,我们可以看到,我们需要将超过 列表中的每一个元素。 除了最后一个元素中,由于第1族元素 已排序的列表。 线两条,我们认为未排序的第一个元素 部分的列表中是最低的,因为我们没有与我们的 例如,我们有一些比较。 第三行开始第二个循环中,我们遍历 每一个未排序的元素。 我们知道后,我迭代,排序的部分 我们的名单必须有i个元素,因为每一步 一种元素进行排序。 因此,第一个未排序的元素必须是在位置i加1。 第四行中,我们比较了当前元素的最低 元素,我们已经看到了这么远。 如果当前元素是小于最小 元素,那么我们记住当前的新元素 最低线5。 最后,在六,七行,我们交换最低 元件与所述第一未排序的元件,从而 将其添加到列表的排序部。 一旦我们有一个算法,一个重要的问题要问 自己作为程序员了多长时间? 首先,我们会问这样的问题如何需要多长时间,这 在最坏的情况下运行的算法来? 还记得我们代表这个运行 大O符号的时间。 为了确定最小的未分类的元素, 基本上比较列表中的每个元素 在列表中的所有其它元素。 直观地说,这听起来像一个O n的平方操作。 在我们的伪代码,我们也有一个循环嵌套在 另一个循环,这的确听起来像一个O n的平方操作。 但是,请记住,我们并不需要在 整个列表时确定的最低未分类的元素吗? 一旦我们知道这4排序,例如,我们没有 需要再次来看待它。 那么,这降低了运行时间? 在我们的名单长度为6,我们需要把五个 比较的第一个元素,四个比较 第二个元素,依此类推。 这意味着,总的步数的总和 从1到的列表的长度减1的整数。 我们可以代表这一个总和。 我们不会进入求和。 但事实证明,这个总和是相等的n倍 N减去2比1。 或等价超过2,N的平方减去n超过2。 在谈到渐近运行,这n的平方项 将主宰这n个任期。 因此,选择排序是O n的平方。 回想一下,在我们的例子中,选择排序仍然需要 检查一个数字,已经排序 需要被感动。 因此,这意味着,如果我们对一个已经跑了选择排序 排序的列表,这将需要相同数量的步骤,因为它 将运行在一个完全未排序的列表。 因此,选择排序有最好的情况下表现为n的平方, 我们所代表的与欧米茄Ň平方。 这就是它的选择排序。 只是其中的的算法,我们可以 使用对列表进行排序。 我的名字是汤米,这是CS50。