>> [音乐播放]
>> 道格·劳埃德：所以插入排序是另一种 算法，我们可以用它来一个数组排序。
这种算法背后的想法 是建立你排序的数组
到位，换挡元件出 因为你走的路，以腾出空间。
这是稍有不同 从选择排序或冒泡
排序，例如，其中 我们调整了位置，
我们正在做掉期交易。
>> 在这种情况下，我们实际上正在 做的是滑动元件
过，闪开。
请问这个算法 在伪代码工作？
那么就让我们武断地说， 该阵列的第一个元素是排序。
我们正在建设到位。
>> 我们会在一个时间去一个因素， 构建它，所以第一件事，我们看到
是一个元件阵列。
根据定义，一个一 元件阵列排序。
>> 然后，我们会重复这个过程until-- 我们会重复以下过程
直到所有的元素进行排序。
看看下一个未排序的元素， 将其插入到排序部，
通过移位所需数量的 元素的出路。
希望这个可视化 将帮助您看看到底是什么
与插入排序怎么回事。
>> 如此反复，这是我们的 整个排序的数组，
所有元素的表示为红色。
而让我们跟随 步骤我们的伪代码。
我们做的第一件事，就是我们所说的 该阵列的第一个元素，排序。
所以，我们只是会说 五，你现在来分类的。
>> 然后我们来看下 阵列的未分类的元素
我们要插入 进入排序的部分，
通过移动元素了。
所以2是下一个未排序 数组的元素。
显然，前所属 五，所以我们是怎么做
是那种举行两场预留第二， 移5以上，然后插入两个
前五位，哪里应该去。
现在，我们可以说，二是排序。
>> 因此，大家可以看到，我们只是到目前为止 看着阵列的两个元素。
我们还没有看的 休息可言，但我们已经
得到了这两个因素排序 变速机构的方式。
>> 因此，我们再次重复这个过程。
看看接下来的无序 元素，这是之一。
我们认为，预留第二， 转变所做的一切，并把一只
它应该去。
>> 同样，还是，我们只是不断 看了一，二，五。
我们不知道还有什么是未来， 但我们已经分类的这三个要素。
>> 接下来排序的元素 三，因此我们将其放在一边。
我们将通过转移我们 需要向其中，这个时间
是不是一切如前 两种情况下，它只是五。
然后，我们将坚持三， 两者之间的和五个。
>> 六是下一个未排序 元件到阵列。
而事实上6大于5，所以 我们甚至不需要做任何交换。
我们可以直接钉六个直角三角形上 排序部分的端部。
>> 最后，四是 最后一个未排序的元素。
因此，我们将其放在一边，转移了 元素我们需要转移过来，
然后放四个它属于的地方。
而现在看，我们已经排序 的所有元素。
与插入通知 排序，我们没有
去来回跨越阵列。
我们只去了整个阵列 有一次，我们转向事物
那我们就已经遇到，为了 以腾出空间给新的元素。
>> 那么什么是最坏的情况下 场景与插入排序？
在最坏的情况下，该 阵列是相反的顺序。
你必须改为每个n个元素 最多n个位置，每一次我们
使插入。
这是一个很大的转变。
>> 在最好的情况下， 数组是完全排序。
而有点像发生了什么 与在实施例5和6，
在这里，我们可以只把它钉住 无需做任何转换，
我们会基本上做到这一点。
>> 如果你想象我们 数组是一至六，
我们会通过开始 声明一个排序。
二来一前一后，所以我们可以只 说好，还有一个和两个排序。
三，三生经过两次的话，OK， 一个，两个和三个排序。
>> 我们没有做任何掉期，我们 只是移动这一独断专行
之间的排序，排序的，因为我们去。
尽可能有效地在我们的例子中那样， 转弯元素的蓝色，因为我们继续。
那么什么是最坏的情况下运行时，又如何呢？
请记住，如果我们要转向各 n个元素可能是N个位置，
希望这给你 一个想法，最坏的情况下
运行时间为n的大澳方。
>> 如果数组是完全 排序，所有我们需要做的
是看每一个元素 一次，然后我们就大功告成了。
因此，在最好的情况下，它是n个欧米茄。
>> 我是道格·劳埃德。
这是CS50。