时间戳

首页 > 解决方案 > 插入排序两种不同实现的效率分析

python - 插入排序两种不同实现的效率分析

问题描述

我为 Python 中的简单插入排序算法提出了两个实现。我的问题：第二个实现比第一个更有效吗？因为在第一个实现中似乎是这样，对于 while 循环的每次迭代，程序必须执行两个赋值：list[i]被赋值，list[i-1]反之亦然（除了减i1）。

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 循环的每次迭代进行一次赋值：（同样除了在 while 循环终止后list[index + 1] = list[index]减1 和一次额外的赋值：） 。indexlist[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更准确地实现插入排序？

标签： pythonalgorithmsortinginsertion-sort

解决方案

你的推理是正确的。然而，即使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

推荐阅读