Jua*_*tos 5 algorithm insertion-sort
假设我们有一个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/
自从提出这个问题以来已经有一段时间了，但是其他答案都没有包含证明这个奇怪的算法实际上对列表进行排序的证据。所以就这样吧。
\n\n假设原始列表是v 1 , v 2 , ..., v n。然后，在算法的i 个步骤之后，我声称该列表如下所示：
\n\n\n\n\nw 1,1 , w 1,2 , ..., w 1, r (1) , v \xcf\x83(1) , w 2,1 , ... w 2, r (2) , v \xcf \x83(2) , w 3,1 ... ... w i , r ( i ) , v \xcf\x83( i ) , ...
\n
其中 \xcf\x83 是v 1到vi的排序排列，w是元素v j且j > i。换句话说，v 1到v i按排序顺序找到，可能与其他元素交错。此外，对于每个j和k ， w j,k \xe2\x89\xa4 v j。因此，每个正确排序的元素前面都有一个小于或等于它的元素块（可能是空的）。
\n\n这是算法的运行，排序后的元素以粗体显示，前面的元素块以斜体显示（非空）。您可以看到每个斜体元素块都小于其后面的粗体元素。
\n\n\n\n\n[4, 8, 6, 1, 2, 7, 5, 0, 3, 9]
\n
\n [ 4 , 8, 6, 1, 2, 7, 5, 0, 3, 9]
\n [ 4 , 6 , 1, 2, 7, 5, 0, 3 , 8 , 9]
\n [ 4 , 1, 2 , 6 , 7, 5, 0, 3 , 8 , 9]
\n [ 1 , 4 , 2 , 6 , 7, 5, 0, 3 , 8 , 9]
\n [ 1 , 2 , 4 , 6 , 7, 5, 0, 3 , 8 , 9]
\n [ 1 , 2 , 4 , 6 , 5, 0 , 3 , 7 , 8 , 9]
\n [ 1 , 2 , 4 , 5 , 6 , 0, 3 , 7 , 8 , 9]
\n [ 0 , 1 , 2 , 4 , 5 , 6 , 3 , 7 , 8 , 9]
\n [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]
\n [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]
如果我的说法是正确的，那么算法就会排序，因为在n步之后，所有vi都按顺序排列，并且没有剩余元素需要交错。但这种说法真的是真的吗？
\n\n好吧，我们用归纳法来证明一下。当i = 0时，这当然为真。假设i为真。然后，当我们运行第 ( i + 1) 步骤时，我们选择v i +1并将其移动到它适合的第一个位置。它肯定会通过j \xe2\x89\xa4 i和v j < v i +1的所有v j（因为这些是按假设排序的，并且每个前面仅包含较小或相等的元素）。它无法传递任何带有j \ xe2 \x89\xa4 i和v j \xe2\x89\xa5 v i +1的 v j ，因为在v j之前的块中有一些位置可以容纳它。因此v i +1最终相对于所有v j和j \xe2\x89\xa4 i进行排序。因此它最终出现在下一个v j之前的元素块中的某个位置，并且由于它最终出现在第一个这样的位置，因此保留了块上的条件。量子电子器件。
\n\n不过，我不会责怪你的教授标记错误。如果您要发明一种前所未见的算法，那么您就需要证明它的正确性！
\n\n（该算法需要一个名称，所以我建议fitsort，因为我们将每个元素放在它适合的第一个位置。）
\n