插入排序中比较和交换的区别

Question

下面给出的是应用于数组A(从零开始的索引)的插入排序算法的伪代码。定义比较(a，b)：如果a>b返回1，否则返回-1

    for i : 1 to length(A)
    j = i - 1
    while j > 0
           if compare(A[j-1], A[j]) > 0
                swap(A[j], A[j-1])
                j = j - 1
           else break

给定一个整数数组A，当在A上应用上述算法时，找出比较函数调用的数量和交换函数调用的数量之间的差异。

让我们以A= {1，2，4，3}为例。如果我们像上面那样在A上应用插入排序，我们将按以下顺序调用比较函数和交换函数的隔离

compare (A[0], A[1])
compare (A[1], A[2])
compare (A[2], A[3])
swap       (A[2], A[3])
compare (A[1], A[2])

这里比较函数被调用4次，交换函数被调用1次。答案是4-1 = 3。

我需要在不运行实际的插入排序算法的情况下找到最优的差异，该算法需要O(n^2)。

Answer 1

对于从2到length(A)的每个i，除了从swap到1的所有元素中当前元素最小的情况外，compare调用的数量将比swap调用的数量多1(在这种情况下，当j变为0时，我们退出循环)。答案将是length(A)-1 - minimal number occurrences。

minElement = A[1] // one-based array
result = length(A) - 1
for i = 2 to length(A)
    if A[i] < minElement 
        minElement = A[i]
        result = result - 1

Answer 2

在while循环中放置一个计数器，在if条件中放置另一个计数器。这两项的减法将会给出答案。