下面给出了应用于数组 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) 的实际插入排序算法的情况下找到最佳差异。
最佳答案
对于从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
关于algorithm - 插入排序中比较和交换的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45298497/