[Powered by Google Translate] [插入排序] [和汤米MacWilliam] [哈佛大学] [这是CS50.TV] 让我们来看看插入排序，算法的号码列表和排序。 简单的算法，记住，是一步一步的过程来完成任务。 后面插入排序的基本思想，是将我们的名单分为两部分， 一个的排序部分和未排序的部分。 

该算法在每个步骤中，一个数字移动 在未排序的部分排序的部分 直到最后整个列表进行排序。 这里是六个未排序的数字列表 -  23，42，4，16，8，和15。 因为这些数字是不是所有的升序排列，它们排序。 因为我们还没有开始整理，我们会考虑所有的六大要素，我们未分类的部分。 

一旦我们开始整理，我们把这些排序的数字，剩下的这些。 所以，让我们开始有23个，在列表中的第一个元素。 我们没有尚未我们的排序部中的任何元素， 让我们简单地认为23是我们的排序部分的开始和结束的。 现在，我们的排序部分有一个数字，23， 我们未分类的部分有这五个数字。 现在让我们插入到我们的未分类的部分，42岁，在未来数排序的部分。 

要做到这一点，我们需要比较的42到23  - 到目前为止，我们的排序部分中的唯一元素。 四是大于23，所以我们可以简单地追加42月底 的排序的列表中的部分。太好了！ 现在，我们的排序部分也有两个元素，我们未分类的部分有四个元素。 所以，现在让我们转移到了4，未排序的部分中的下一个元素。 所以，这应该被放置在排序部？ 

请记住，我们想要把这个数的排序顺序 因此，在任何时候，我们的排序部分保持正确排序。 如果我们把4个到42个的权利，那么我们的名单将出。 所以，让我们继续在我们的排序部分从右到左移动。 随着我们的，让我们每个号码转移下来的地方以腾出空间给新的号码。 好了，4也是小于23，因此，我们不能把它在这里。 让我们继续前进的23个正确的地方。 

这意味着我们想放置4到第一个插槽的排序部分。 请注意，这个空间是如何在列表中已经是空的， 因为我们一直在移动排序的元素，因为我们已经遇到他们。 好的。因此，我们已经完成一半了。 让我们继续我们的算法插入16到排序的部分。 16为小于42，所以让我们转移42至正确的。 16为小于23，所以我们也该元素的转移。 

现在，图16是大于4。因此，它看起来像我们想在4和23之间插入16。 通过排序的列表部移动的同时，由右至左， 4是第一个数字，我们已经看到，数小于 我们正在试图插入。 所以，现在我们可以插入16到这个空的插槽， 请记得，我们已经创建了移动的元素在排序部分 我们遇到他们。 

好的。现在，我们有四个排序的元素和两个未排序的元素。 所以，让我们继续前进8成排序的部分。 八是小于42。 八是小于23。 和图8是小于16。 但是，图8是大于4。 所以，我们想在4和16之间插入8。 现在，我们只是有一个更多的元素进行排序 -  15。 十五是小于42， 十五是小于23。 和15是小于16。 但15是大于8。 

所以，在这里我们想使我们的最后插入。 我们就大功告成了。 我们有没有更多的元素在未排序的部分， 和我们的排序条件部分是在以正确的顺序。 从最小到最大的数字是有序的。 所以，让我们来看看一些伪代码描述的步骤，我们只是执行。 

在第1行中，我们可以看到，我们需要遍历列表中的每个元素 除了第一个，因为第一个元素在未排序的部分，都只是 的排序部中的第一元素。 在第2和第3行，我们正在跟踪我们目前在未排序的部分。 元素代表的数量，我们目前正在进入排序的部分， j表示我们的索引中未排序的部分。 

在第4行中，我们遍历由右至左排序的部分。 我们要停止迭代一次的元素的左侧我们当前的位置 是小于我们试图插入的元素。 在第5行中，我们把每一个元素我们遇到的一个空间，以正确的。 这样一来，当我们找到的第一个元素，我们将有一个明确的空间插入到 不到我们正在元素。 在第6行，我们正在更新我们的柜台，继续向左移动通过排序的部分。 最后，第7行，我们的元素插入到列表中的排序部分。 

我们知道它的好插入位置j， 因为我们已经提出的元素，以前是有一个空格的右侧。 请记住，我们正在通过由右至左排序的部分， 但我们正在通过未排序的部分由左到右。 好的。现在，让我们来看看在多长时间运行的算法了。 多久需要运行这个算法在最坏的情况下，我们首先会问的问题。 回想一下，我们与大O表示法表示这个运行时间。 为了我们的列表进行排序，我们不得不遍历未排序的部分中的元素， 并为每个这些元素，可能超过的排序部中的所有元素的。 直观地说，这听起来像一个O（N ^ 2）操作。 

在我们的伪代码，我们有一个循环嵌套在另一个循环， 而事实上，听起来像一个O（N ^ 2）操作。 然而，排序的部分列表中没有包含整个列表，直到最后一刻。 尽管如此，我们可能在开始的时候排序的部分中插入一个新元素 在每次迭代的算法， 这意味着我们不得不看每个元素目前在已排序的部分。 所以，这意味着我们有可能做一个比较的第二个元素， 两个比较的第三个元素，依此类推。 所以，总的步数是从1到的列表的长度减1的整数的总和。 我们可以代表这一个总和。 

在这里，我们不会去求和，但事实证明，这个总和是相等的 超过2 N（n  -  1个），这相当于n ^ 2的/ 2  -  n / 2个。 在谈到关于渐近运行时， 这n ^ 2项将主宰这n个任期。 所以，插入排序是大O（N ^ 2）。 如果我们遇到一个已排序的列表中插入排序。 在这种情况下，我们只需要建立从左至右排序的部分。 所以，我们只需要n个步骤的顺序。 

这意味着，插入排序的n有一个最好的情况下的性能， 我们与Ω（n）的代表。 这就是它插入排序， 只是我们的许多算法可以对列表进行排序。 我的名字是汤米，这是CS50。 [CS50.TV] 啊，你只是不能停止，一旦它开始。 哦，我们这样做 - “”轰！“