插入排序理论分析，移位总数。
给定以下数组：
[14 17 21 34 47 19 71 22 29 41 8]以下摘录自Thomas Cormen解锁的“算法”(略作编辑，开始和停止标志不在文本中)：
当数组开头为“几乎排序”时，插入排序是一个很好的选择。START假设每个数组元素从它在排序数组中结束的位置的k个位置开始。那么，给定元素在内循环的所有迭代中移动的总次数最多是k。因此，所有元素在所有内环迭代中移动的总次数最多为kn，这反过来又告诉我们，内环迭代的总次数最多为kn (如果k是常数，则每个内环迭代正好将一个元素移动一个position).STOP，那么插入排序的总运行时间将仅为Θ(n)，因为Θ-表示法包含常数因子k。事实上，只要没有太多这样的元素，我们甚至可以容忍一些元素在数组中长距离移动。特别是，如果L元素可以在数组中的任何位置移动(这样，这些元素中的每个元素最多可以移动n-1位置)，而其余的n-L元素最多只能移动k个位置，那么如果k和L都是常数，则的移位总数最多为* (n - 1) + (n - L) *k= (k + L) *n- (k + 1) * L，即Θ(n)。
这些书试图解释它是如何制作一个公式，它呈现在课文的底部。我想要一些帮助，以更好地理解它说了什么，很可能，它可以帮助一个特定的例子使用上面的示例数组，以便对k和n变量发生什么作用。你能帮我更好地理解以上摘录的分析吗？
更确切地说，让我感到困惑的是，开始标志和停止标志之间的行，这些是行：
假设每个数组元素.这反过来告诉我们，内环迭代的总次数最多是kn(因为每个内环迭代都会将一个元素逐个位置移动)。
(这些线下的任何东西都是完全理解的，一直到最后。)
回答 1
Stack Overflow用户
发布于 2017-08-18 23:45:51
让我们考虑插入排序算法。
算法: InsertionSort(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 whileA0.I-1的内环-移动元素，直到Ai处于正确的位置。因此，如果给定的元素在距其正确位置的k个位置上，我们将有一个最大的k比较和交换。对于n个元素，它将是k*n。
希望能帮上忙！
https://stackoverflow.com/questions/45761780
复制
腾讯云开发者
