插入排序两种不同实现方式的效率分析

Question

我在 Python 中为一个简单的插入排序算法提出了两个实现。我的问题：第二个实施是否比第一个更有效？因为在第一个实现中，对于 while 循环的每次迭代，程序都必须执行两个分配：list[i] 被分配给 list[i-1]，反之亦然（除了递减 i 通过 1).

def insertion1(list):

    for i in range(1,len(list)):     

        while i >= 1 and list[i] < list[i-1]:
            list[i],list[i-1] = list[i-1],list[i]
            i -= 1

但在第二种实现中，程序必须为 while 循环的每次迭代只进行一次赋值：list[index + 1] = list[index]（同样除了将 index 递减 1 和在终止后进行一次附加赋值while 循环的：list[index + 1] = temp)。

def insertion2(list):

    for i in range(1,len(list)):
        temp = list[i]
        index = i - 1

        while index >= 0 and list[index] > temp:
            list[index + 1] = list[index]
            index -= 1
        list[index + 1] = temp

这是否意味着 insertion1 与 insertion2 相比，大致必须执行两倍的赋值语句，从而使 insertion2 成为更准确的插入排序实现？

Answer 1

你的推理是正确的。然而，即使 insertion2 也不是最优的。内部循环每次迭代执行 2 比较（index >= 0 和 list[index] > temp）。可以将其减少到（几乎）一个比较：

    if temp < list[0]:
        # We don't care about values anymore. Every element shall be shifted.
        while index >= 0:
            list[index + 1] = list[index]
            index -= 1
    else:
        # We don't care about indices anymore. list[0] is a natural sentinel
        while temp < list[index]:
            list[index + 1] = list[index]
            index -= 1
    list[index] = temp

插入排序两种不同实现方式的效率分析

Efficiency Analysis of Two Different Implementations of Insertion Sort

python

algorithm

sorting

insertion-sort