python - 排序算法效率对比

Question

我一直在尝试简单的排序算法以更加熟悉它们，并尝试根据算法的描述而不是伪代码来创建插入排序。我做了一个有效的算法，我认为符合描述:

import random
nums = []
for i in range(10000):
    nums.append(random.randrange(0, 1000))

def getSortedIndexForEle(ele, sorted):
    for i in range(0, len(sorted)):
        if ele < sorted[i]:
            return i
    return len(sorted)

def sort(lst):
    sorted = []
    for ele in lst:
        sorted.insert(getSortedIndexForEle(ele, sorted), ele)
    return sorted

print(sort(nums))

但是代码与算法组合不匹配(但仍然产生了正确的结果)所以我又进行了一次尝试:

import random
nums = []
for i in range(10000):
    nums.append(random.randrange(0, 1000))

def sort(lst):
    for i in range(1, len(lst)):
        ele = lst[i]
        j = i - 1
        for k in range(j, -2, -1):
            if ele >= lst[k]:
                break
            lst[k + 1] = lst[k]
        lst[k + 1] = ele


sort(nums)
print(nums)

我相信这个是正确的，我将它与伪代码进行了比较，它实际上做了同样的事情。

我的问题是我制作的第一个算法，它不适合该算法，在我的机器上执行时间大约是实际时间的一半(使用长度为 10000 的列表，每个元素都是一个随机数)。这怎么可能？我的第二个算法不正确吗？我什至尝试了该算法的一个 Python 示例，它也比我的第一个示例花费了更长的时间...

Answer 1

第二个就地排序，第一个没有。

在第二种算法中，您将每个元素插入到原始数组中，之后的每个元素都必须移动以容纳它。时间复杂度为 O(n2)，但它只需要常数 O(1) 的额外内存。

在第一个中，您在单独的数组中插入一个元素，并且只需要移动已经排序的较大元素。所以时间复杂度介于 O(n) 和 O(n2) 之间，但它需要 O(n) 额外的内存。