[音乐播放] 

道格·劳埃德：所以插入排序是另一种 算法，我们可以用它来一个数组排序。 这种算法背后的想法 是建立你排序的数组 到位，换挡元件出 因为你走的路，以腾出空间。 这是稍有不同 从选择排序或冒泡 排序，例如，其中 我们调整了位置， 我们正在做掉期交易。 

在这种情况下，我们实际上正在 做的是滑动元件 过，闪开。 请问这个算法 在伪代码工作？ 那么就让我们武断地说， 该阵列的第一个元素是排序。 我们正在建设到位。 

我们会在一个时间去一个因素， 构建它，所以第一件事，我们看到 是一个元件阵列。 根据定义，一个一 元件阵列排序。 

然后，我们会重复这个过程until-- 我们会重复以下过程 直到所有的元素进行排序。 看看下一个未排序的元素， 将其插入到排序部， 通过移位所需数量的 元素的出路。 希望这个可视化 将帮助您看看到底是什么 与插入排序怎么回事。 

如此反复，这是我们的 整个排序的数组， 所有元素的表示为红色。 而让我们跟随 步骤我们的伪代码。 我们做的第一件事，就是我们所说的 该阵列的第一个元素，排序。 所以，我们只是会说 五，你现在来分类的。 

然后我们来看下 阵列的未分类的元素 我们要插入 进入排序的部分， 通过移动元素了。 所以2是下一个未排序 数组的元素。 显然，前所属 五，所以我们是怎么做 是那种举行两场预留第二， 移5以上，然后插入两个 前五位，哪里应该去。 现在，我们可以说，二是排序。 

因此，大家可以看到，我们只是到目前为止 看着阵列的两个元素。 我们还没有看的 休息可言，但我们已经 得到了这两个因素排序 变速机构的方式。 

因此，我们再次重复这个过程。 看看接下来的无序 元素，这是之一。 我们认为，预留第二， 转变所做的一切，并把一只 它应该去。 

同样，还是，我们只是不断 看了一，二，五。 我们不知道还有什么是未来， 但我们已经分类的这三个要素。 

接下来排序的元素 三，因此我们将其放在一边。 我们将通过转移我们 需要向其中，这个时间 是不是一切如前 两种情况下，它只是五。 然后，我们将坚持三， 两者之间的和五个。 

六是下一个未排序 元件到阵列。 而事实上6大于5，所以 我们甚至不需要做任何交换。 我们可以直接钉六个直角三角形上 排序部分的端部。 

最后，四是 最后一个未排序的元素。 因此，我们将其放在一边，转移了 元素我们需要转移过来， 然后放四个它属于的地方。 而现在看，我们已经排序 的所有元素。 与插入通知 排序，我们没有 去来回跨越阵列。 我们只去了整个阵列 有一次，我们转向事物 那我们就已经遇到，为了 以腾出空间给新的元素。 

那么什么是最坏的情况下 场景与插入排序？ 在最坏的情况下，该 阵列是相反的顺序。 你必须改为每个n个元素 最多n个位置，每一次我们 使插入。 这是一个很大的转变。 

在最好的情况下， 数组是完全排序。 而有点像发生了什么 与在实施例5和6， 在这里，我们可以只把它钉住 无需做任何转换， 我们会基本上做到这一点。 

如果你想象我们 数组是一至六， 我们会通过开始 声明一个排序。 二来一前一后，所以我们可以只 说好，还有一个和两个排序。 三，三生经过两次的话，OK， 一个，两个和三个排序。 

我们没有做任何掉期，我们 只是移动这一独断专行 之间的排序，排序的，因为我们去。 尽可能有效地在我们的例子中那样， 转弯元素的蓝色，因为我们继续。 那么什么是最坏的情况下运行时，又如何呢？ 请记住，如果我们要转向各 n个元素可能是N个位置， 希望这给你 一个想法，最坏的情况下 运行时间为n的大澳方。 

如果数组是完全 排序，所有我们需要做的 是看每一个元素 一次，然后我们就大功告成了。 因此，在最好的情况下，它是n个欧米茄。 

我是道格·劳埃德。 这是CS50。