CLRS 插入排序实现

Question

我正在研究 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)

谢谢

Answer 1

两者都是正确的，并且都在 O(n^2) 时间内运行，但是第二种实现更好，因为您只对列表的每个元素进行 1 次交换，而对于第一种实现，您这样做O(n^2) 交换。第一个实现将 out-of-place 数字与下一个数字交换，直到数字位于正确的位置，而第二个实现在将数字交换到其最终正确位置之前找到 out-of-place 数字的正确索引。尽管交换的时间复杂度为 O(1)，但它们比简单地递减一个数字花费的时间更长。

Answer 2

所提议的函数都没有实际重现 CLRS 中提供的算法。

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

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

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

CLRS 插入排序实现

CLRS Insertion Sort Implmentation

algorithm

insertion-sort

clrs