arrays - k 使用插入排序弄乱排序的数组

Question

在这个熟悉的问题中，数组中的每个元素最多偏离其正确位置 k 个位置，无论是向左还是向右，我不完全理解插入排序算法的工作原理。

我把它画在纸上，调试了一步。它似乎确实有效，时间复杂度的顺序也是 O(n.k)。

但我的问题是，在这个问题中，元素可能在左边或右边相隔 k 个位置。然而，插入排序只检查左边。它是如何做到正确的？ 请你向我解释一下，尽管我们只向左看，但这个算法仍然有效，我可以说服自己吗？

PS : 这里不相关 : 如果我不知道这个算法，我会想到像选择排序这样的东西，对于给定的元素，我，你在左右，选择最小的元素。

PS:更无关紧要:我知道基于最小堆的方法。同样的问题，为什么我们只看左边？

Answer 1

当算法处理较小的项目时，正确位置左侧的项目被推向右侧。 (假设我们按升序排序。)例如，如果 k 是 3 并且初始数组是

D A B E H C F G

让我们检查一下 D 是如何到达数组中的位置 3 的。 (使用从零开始的索引，D 从索引 0 开始，需要移动到数组中的索引 3。)

第一遍从E开始，发现它可以交换A和D导致

A D B E H C F G

第二遍从 H 开始，交换 B 和 D

A B D E H C F G

第三遍从 C 开始，将 C 与 H、E 和 D 交换

A B C D E H F G

现在你看到 D 已经在它应该在的地方了。

情况总是如此。随着处理较小的元素，任何从其最终位置左侧开始的元素都将被向右推(到其最终位置)。否则，较小的元素不在它们的正确位置。并且元素(如 D)不会被推过它的正确位置，因为算法不会将该元素与更大的元素交换。