CLRS插入排序嵌入

Question

我正在CLRS中进行插入排序。我不知道哪一个是正确的-

来自CLRS的Algo -

​

执行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)

谢谢

Answer 1

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

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

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

第二个函数只执行一个交换，它将元素j的值移到正确的位置，但不保留列表的其他前缀的顺序。所以它要快得多，但会产生一个不正确的结果。(它碰巧使用测试向量生成排序的输出，这很有趣，但是如果您查看每个插入点上的连续前缀，您会发现它并不真正有效。例如，尝试只对[2, 3, 1]进行排序。)

Answer 2

两者都是正确的，并且都在O(n^2)时间内运行，但是第二个实现更好，因为您只对列表中的每个元素执行一个交换，而对于第一个实现则执行O(n^2)交换。第一个实现将离开位置的数字与下一个数字互换，直到该数字位于正确的位置，而第二个实现在将该数字交换到其最终正确位置之前为该离开位置号码找到正确的索引。虽然掉期是O(1)时间，但其花费的时间比简单地减少一个数字所花费的时间要长。