二进制插入排序实现 Python

Question

在研究算法时，我发现了一个算法，它基本上是一种插入排序，但它在向后移动元素时使用二进制搜索而不是 WHILE 循环语句。

我编写了以下实现代码，它在给定的输入下运行良好。

我的问题是 1) 我的代码有什么改进吗？ 2）我仍然不明白为什么尽管使用了二进制搜索它仍然有二次时间。我想我需要帮助来理解这一点。

提前感谢您的宝贵意见:)

A=[3,25,18,41,52,26,38,57,9,49]
def InsertionSort_improved(A):
    for k in range(1,len(A)):
        key = A[k]
        low = 0
        high = k-1
        BinarySearch(A,low,high,key,k)

def BinarySearch(A,low,high,key,k):
    if low<high:
        mid= (low+high)//2
        if A[mid] == key:
            for i in range(k,mid,-1):
                A[i] = A[i-1]
            A[i-1] = key
        elif A[mid] < key:
            BinarySearch(A, mid+1, high, key, k)
        else:
            BinarySearch(A, low, mid, key, k)
    else:
        mid=(low+high)//2
        if A[mid]>key:
            for j in range(k,mid,-1):
                A[j] = A[j-1]
            A[j-1] = key

InsertionSort_improved(A)
print(A)

Answer 1

长话短说：因为这两行。

for j in range(k,mid,-1):
    A[j] = A[j-1]

元素的插入是这样的：

找到插入新元素的位置；
移动大量元素以为新元素腾出空间。

您找到的代码使用二进制搜索来加快第一步，变成 O(log(n)) 而不是 O(n)。

但是它仍然需要移动元素，这是通过一个简单的 for-loop 完成的，这需要 O(n) 时间。

注意，对链表而不是数组进行插入排序时，不再需要移位，因此第二步变为O(1)...但是对于链表，二分查找是不可能的, 所以第一步仍然是 O(n).

结论：在数组和链表上，插入排序仍然是二次算法。

二进制插入排序实现 Python

Binary Insertion Sort Implementation Python

python

sorting

binary-search

insertion-sort