就地插入排序比创建新列表的插入排序慢？

Question

def insertion(sequence):
    for i in range(1, len(sequence)):
        key = sequence[i]
        j = search(sequence,0,i-1,key)
        while i > j:
            sequence[i], sequence[i-1] = sequence[i-1], sequence[i]
            i = i - 1
    return sequence

def insertion2(sequence):
    new_li = [sequence[0]]
    for i in range(1,len(sequence)):
        key = sequence[i]
        j = search(new_li,0,len(new_li)-1,key)
        new_li.insert(j,key)
    return new_li

我有 2 次插入和 2 种方法。插入比插入 2 花费的时间长得多（5.346 与 0.0313 相比）。需要帮助找出原因

PS：查找基本上是二分查找的辅助功能

Answer 1

你在第一个中做了更多的工作。当您找到插入点时，您将不断交换项目以将项目从 [i] 移动到 [j] 在第二个中，您使用 insert 函数将一个项目插入第二个大批。这只是将数组中的所有内容都向下移动了一个。

换句话说，您在第一个中的插入是这样的：

while i > j
    temp = sequence[i]
    sequence[i] = sequence[i-1]
    sequence[i-1] = temp
    i = i-1

因此，您为项目必须移动的每个位置执行四次数组访问和三次赋值。

在第二个中，insert 函数基本上是这样做的：

x = len(new_li)-1
while x < j
    new_li[i+1] = new_li[i]
    i = i - 1

在这里，您只需对每个必须移动的项目进行两次数组访问和一次赋值。

您可以通过编写将要移动的项目复制到临时变量中的代码以及与我展示的第二个循环基本相同的循环将内容从 j 移动到 i下一个space，然后将保存的项目放入sequence[j]。

就地插入排序比创建新列表的插入排序慢？

Inplace insertion sort slower than insertion sort that creates a new list?

python-3.x

sorting

insertion-sort