k 使用插入排序弄乱排序的数组
k messed sorted array using Insertion sort
在一个熟悉的问题中，数组中的每个元素最多偏离其正确位置 k 个位置，无论是向左还是向右，我不完全理解插入排序算法的工作原理。
画在纸上，一步步调试。它似乎确实有效，时间复杂度的顺序也是 O(n.k)。
但我的问题是，在这个问题中，元素可能在左侧或右侧相距 k 个位置。然而，插入排序只检查左边。它是如何做到正确的？ 你能给我解释一下，这个算法是如何工作的，虽然我们只看左边，但我可以说服自己？
PS : 这里不相关 : 如果我不知道这个算法，我会想到像选择排序这样的东西，对于给定的元素,i,你看左右k个位置，选择最小的元素。
PS : 更无关紧要: 我知道基于最小堆的方法。还是一样的问题，为什么只看左边？
在插入排序中实际发生的是我们比较一个元素和它左边的每个元素。所以发生的是该元素左侧的 列表被排序，而该元素右侧的列表未被排序 。然后我们继续下一个元素并再次重复相同的过程。这样做直到我们到达列表中的最后一个元素。因此我们得到排序列表。
只需要向左看是错误的假设。也可以从开头索引开始往右看
但是，有一种叫做 循环不变性 的东西（阅读更多相关信息）。插入排序的不变性是它在其左侧或右侧保留一个已排序的子数组（随着算法运行而增长）。
这是 link 的阅读内容，可以清除它。 https://www.hackerrank.com/challenges/correctness-invariant
当算法处理较小的项目时，正确位置左侧的项目被推向右侧。 （假设我们按升序排序。）例如，如果 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）不会被推过它的正确位置，因为算法不会将该元素与更大的元素交换。
在一个熟悉的问题中，数组中的每个元素最多偏离其正确位置 k 个位置，无论是向左还是向右，我不完全理解插入排序算法的工作原理。
画在纸上，一步步调试。它似乎确实有效，时间复杂度的顺序也是 O(n.k)。
但我的问题是，在这个问题中，元素可能在左侧或右侧相距 k 个位置。然而，插入排序只检查左边。它是如何做到正确的？ 你能给我解释一下，这个算法是如何工作的，虽然我们只看左边，但我可以说服自己？
PS : 这里不相关 : 如果我不知道这个算法，我会想到像选择排序这样的东西，对于给定的元素,i,你看左右k个位置，选择最小的元素。
PS : 更无关紧要: 我知道基于最小堆的方法。还是一样的问题，为什么只看左边？
在插入排序中实际发生的是我们比较一个元素和它左边的每个元素。所以发生的是该元素左侧的 列表被排序，而该元素右侧的列表未被排序 。然后我们继续下一个元素并再次重复相同的过程。这样做直到我们到达列表中的最后一个元素。因此我们得到排序列表。
只需要向左看是错误的假设。也可以从开头索引开始往右看
但是，有一种叫做 循环不变性 的东西（阅读更多相关信息）。插入排序的不变性是它在其左侧或右侧保留一个已排序的子数组（随着算法运行而增长）。
这是 link 的阅读内容，可以清除它。 https://www.hackerrank.com/challenges/correctness-invariant
当算法处理较小的项目时，正确位置左侧的项目被推向右侧。 （假设我们按升序排序。）例如，如果 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）不会被推过它的正确位置，因为算法不会将该元素与更大的元素交换。