0

我正在通过 CLRS 中的插入排序算法。我不确定哪个是正确的实现 -

来自 CLRS 的算法 - CLRS 伪代码

实施1：

def Insertion_sort():
list = [3,5,1,7,2,4]
for j in xrange(1,len(list)):
    i = j-1
    while i>=0 and list[i] > list[j]:
        swap(list, i, j)
        j = i
        i = i-1

实施2：

def Insertion_sort2():
list = [3,5,1,7,2,4]
for j in range(1,len(list)):
    i = j-1;
    while i>=0 and list[i]>list[j]:
        i = i-1;
    swap(list, i+1, j)

谢谢

4

2 回答 2

0

两个提议的函数实际上都没有重现 CLRS 中提出的算法。

CLRS 算法中第 5 行到第 8 行的代码对以 index 结尾的列表的子序列进行旋转j。这会将索引处的值插入j列表前缀中的正确点。

你的第一个函数做同样的事情，但不是做一个轮换，而是做一系列的交换。轮换效率更高，因为它只修改每个列表项一次而不是两次。

您的第二个函数仅执行一次交换，它将元素处的值移动j到正确的位置，但不保留列表前缀其余部分的顺序。所以它要快得多，但会产生不正确的结果。（它碰巧用你的测试向量产生一个排序输出的事实很有趣，但是如果你查看每个插入点的连续前缀，你会发现它并没有真正起作用。[2, 3, 1]例如，尝试仅排序。 )

于 2016-01-22T02:02:13.340 回答
-1

两者都是正确的并且都在 O(n^2) 时间内运行，但是第二个实现更好，因为您只对列表的每个元素进行 1 次交换，而对于第一个实现，您执行 O(n^2) 交换。第一个实现将异位数字与下一个数字交换，直到该数字位于正确的位置，而第二个实现在将数字交换到其最终正确位置之前找到异位数字的正确索引。尽管交换是 O(1) 时间，但它们比简单地减少一个数字需要更长的时间。

于 2016-01-20T07:54:07.067 回答