arrays - 插入排序理论分析，总移位数。

Question

给定以下数组:

[14 17 21 34 47 19 71 22 29 41 8]

以及以下摘自 Thomas Cormen 所著的《算法解锁》一书(稍作编辑，[START] 和 [STOP] 标志不是文本的一部分):

Insertion sort is an excellent choice when the array starts out as ''almost sorted''. [START] Suppose that each array element starts out within k positions of where it ends up in the sorted array. Then the total number of times that a given element is shifted over all iterations of the inner loop is at most k. Therefore, the total number of times that all elements are shifted over all inner-loop iterations, is at most kn, which in turn tells us that the total number of inner-loop iterations is at most kn (since each inner-loop iteration shifts exactly one element by one position).[STOP] If k is a constant, then the total running time of insertion sort would he only Θ(n), because the Θ-notation subsumes the constant factor k. In fact we can even tolerate some elements moving a long distance in the array, as long as there are not too many such elements. In particular, if L elements can move anywhere in the array (so that each of these elements can move by up to n-1 positions), and the remaining n - L elements can more at most k positions, then the total number of shifts is at most L * (n – 1) + (n – L) * k = (k + L) * n – (k + 1) * L, which is Θ(n) if both k and L are constants.

这些书试图解释它是如何制作一个公式的，它出现在文本的底部。我想要一些帮助以更好地理解它所说的内容，很可能它可以帮助使用上述示例数组的特定示例，以便 k 和 n 变量发生了什么。你能帮助我更好地理解上面摘录的分析吗？

更具体地说是什么让我感到困惑，[START] 和 [STOP] 标志之间的线，这些是线:

Suppose that each array element..... which in turn tells us that the total number of inner-loop iterations is at most kn(since each inner-loop iteration shifts exactly one element by one position).

(这些线以下的任何内容从头到尾都是完全理解的。)

Answer 1

让我们考虑一下插入排序算法

算法:插入排序(A)

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

内层循环 - 将 A[0..i-1] 的元素一个一个地移动，直到 A[i] 处于正确的位置。因此，如果给定元素与其正确位置相距至多 k 个位置，我们将进行最多 k 次比较和交换。对于 n 个元素，它将是 k*n。

希望对您有所帮助!