最佳情况下交换和比较的二进制插入排序复杂度

Question

二进制插入排序的复杂度是多少？进行了多少次交换和比较？

可能是O(n(LG n))比较，但我不确定。最坏的情况下，确实是 N^2 掉期。最好的呢？

Answer 1

您可以利用内置函数轻松编写二进制插入排序，例如 bisect_left and list.pop(..) and list.insert(..) :

def bininssort(L):
    n = len(L)
    i,j=0,0
    for i in range(1,n):
        j=i-1
        x=L.pop(i)
        i1=bisect_left(L,x,0,j+1)
        L.insert(i1,x)
    return L

关于最坏的情况，因为在循环的 i-th 迭代中，我们在子数组 A[0..i] 和 0<=i<n 中执行二进制搜索，这应该采取log(i) 操作，所以我们现在知道我们必须在位置 i1 插入一个元素并且我们插入它，但是插入意味着我们必须将它后面的所有元素向右推一个位置，并且这至少是 n-i 次操作（它可能超过 n-i 次操作，具体取决于插入位置）。如果我们只总结这两个，我们得到 \sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(上面log(n!)的Stirling's approximation被使用了)

现在the wiki page说

As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order

所以我认为结论是，在最坏的情况下，二进制插入排序具有 O(n^2) 复杂性。

另请参阅：

insertion sort with binary search
analysis of binary insertion sort

然后我尝试检查它在反向（n,n-1,n-2,..,1）和交替（0,n-1,1,n-2,2,n-3,...）列表上的表现。我将它们（使用 matchgrowth module）拟合到不同的增长率，这部分只是一个近似值。倒序拟合多项式时间，交替序拟合拟线性时间

最好的情况是explained here。如果列表已经排序，那么即使我们不做任何交换，所有的二进制搜索仍在执行，这导致 O(n*log(n)).

此处使用的代码 is available 在此存储库中。

最佳情况下交换和比较的二进制插入排序复杂度

Binary Insertion sort complexity for swaps and comparison in best case

algorithm

sorting

insertion-sort