algorithm - 这等同于插入排序吗？

Question

假设我们有一个索引为 0 的序列 S，取 S[0] 并将其插入 S 中下一个值高于 S[0] 且前一个值低于 S[0] 的位置。形式上，S[i] 应该放在 S[i-1] < S[i] < S[i+1] 这样的地方。继续在列表上对每个项目执行相同的操作。在将元素放在正确位置之前从列表中删除该元素。在对列表进行一次迭代后，列表应该被排序。我最近考试忘记了插入排序(别笑)，我是这样做的。但是，我的教授将其标记为错误。据我所知，该算法确实会生成一个排序列表。

在列表中这样工作:

Sorting [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 5, 4, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 0, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 1, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 3, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Got [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

由于每次将一个元素插入列表中时，列表中最多 (n-1) 个数字可能会被移动，我们必须这样做 n 次，算法应该在 O(n^2) 时间内运行。

我有一个 Python 实现，但我不知何故放错了地方。我稍后会尝试再写一遍，但实现起来有点棘手。有什么想法吗？

Python 实现在这里:http://dpaste.com/hold/522232/ .它是由 reddit.com 的 busy_beaver 在此处讨论时编写的 http://www.reddit.com/r/compsci/comments/ejaaz/is_this_equivalent_to_insertion_sort/

Answer 1

自从有人提出这个问题以来已经有一段时间了，但是其他答案都没有包含证明这个奇怪的算法实际上确实对列表进行排序的证据。就这样吧。

假设原始列表为v₁, v₂, ..., v_n。然后在算法的 i 步之后，我声明列表如下所示:

w_1,1, w_1,2, ..., w_1,r(1), v_σ(1), w_2,1, ... w_2,r(2), v_σ(2), w_3,1 ... ... w_i,r(i), v_σ(i), ...

其中 σ 是 v₁ 到 v_i 的排序排列w 是元素 v_j with j> i。换句话说，v₁ 到 v_i 是按排序顺序找到的，可能与其他元素交错。此外，w_j,k ≤ v_j 用于每个 j 和 k。因此，每个正确排序的元素之前都有一个(可能为空)小于或等于它的元素 block 。

这是算法的运行，排序后的元素以粗体显示，前面的元素 block 以斜体显示(非空)。您可以看到每个斜体元素 block 都小于其后的粗体元素。

[4, 8, 6, 1, 2, 7, 5, 0, 3, 9]
[4, 8, 6, 1, 2, 7, 5, 0, 3, 9]
[4, 6, 1, 2, 7, 5, 0, 3, 8, 9]
[4, 1, 2, 6, 7, 5, 0, 3, 8, 9]
[1, 4, 2, 6, 7, 5, 0, 3, 8, 9]
[1, 2, 4, 6, 7, 5, 0, 3, 8, 9]
[1, 2, 4, 6, 5, 0, 3, 7, 8, 9]
[1, 2, 4, 5, 6, 0, 3, 7, 8, 9]
[0, 1, 2, 4, 5, 6, 3, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

如果我的说法是正确的，那么算法会排序，因为在 n 步之后所有的 v_i是有序的，并且没有剩余的元素要交错。但这个说法真的是真的吗？

好吧，让我们用归纳法证明一下。当 i = 0 时肯定为真。假设对于 i 为真。然后当我们运行 (i + 1)st 步时，我们选择 v_i+1 并移动它到它适合的第一个位置。它肯定会通过所有 v_j 且 j ≤ i 和 v_j <v_i+1(因为这些是按假设排序，每个元素前面只有更小或相等的元素)。它不能通过任何 v_j 且 j ≤ i 和 v_j ≥ v_i+1，因为有一些v_j 之前 block 中适合的位置。所以 v_i+1 最终相对于所有 v_j 且 j ≤ i。所以它在下一个 v_j 之前的元素 block 中的某处结束，并且因为它在 first 这样的位置， block 上的条件被保留。 QED.

但是，我不会责怪您的教授将其标记为错误。如果您要发明一种前所未见的算法，则需要您来证明它的正确性!

(算法需要一个名字，所以我提出fitsort，因为我们把每个元素放在最适合的地方。)