[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]
啊，你只是不能停止，一旦它开始。
哦，我们这样做 - “”轰！“