使 "Insertion sort" 算法更高效 - Python 3.5.2

Question

我尝试在 python 中编写插入排序算法 -

def insertion(list):
    checked = 2
    while (checked <= len(list)):
        for i in range(checked-1):
            if list[checked-1] < list[i]:
                list.insert(i, list[checked-1])
                del list[checked]
        checked+=1
    return list

我测量了执行 1000 个项目排序所花费的时间 - 106.08099999999997 千分之一秒

我发现这很慢，因为 -

def bubbleSort(alist,n):
    for j in range(1,n):
        nextnum = alist[j]
        i = j - 1
        while i>=0 and alist[i]>nextnum:
            alist[i + 1] = alist[i]
            i = i - 1       
        alist[i + 1] = nextnum

只拿了- 83.71800000000007 千分之一秒

有什么方法可以让我的代码更高效/我是否必须使用不同的代码？如果是这样，哪种插入排序实现在 python 中最快？我知道插入排序通常不是最好的算法。这只是为了我的学校作业，以便我更好地理解我们学习的算法。

Answer 1

从列表中插入和删除比仅交换位置的内容更昂贵。这比冒泡排序更快：

def insertion(M):
    for i in range(1,len(M)):
        for j in range(i):
            if M[i] < M[j]:
                M[j],M[j+1:i+1] = M[i],M[j:i]
                break

请注意，这使用了 a,b = b,a 的 "swap" 语法，它将选中的值交换到插入位置，并将剩余值交换到列表中的一个前面。此外，一旦交换完成，就从内部循环中退出。无需继续检查插入位置。您还可以检查要交换的值是否已经大于或等于先前排序的值，并在 true 时跳过内部循环：

def insertion(M):
    for i in range(1,len(M)):
        if M[i] >= M[i-1]:
            continue
        for j in range(i):
            if M[i] < M[j]:
                M[j],M[j+1:i+1] = M[i],M[j:i]
                break

使 "Insertion sort" 算法更高效 - Python 3.5.2

Making "Insertion sort" algorithm more efficient - Python 3.5.2

algorithm

python-3.x

optimization

insertion-sort