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

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 = {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，compare调用的次数将增加一次除了 1 到 i 的所有元素中当前元素最小的情况(在这种情况下我们退出j 变为 0 时的循环)。答案将是 length(A)-1 - minimum 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