sorting - 为什么反转的分布在插入排序中不重要？

Question

根据 Robert Sedwick 的说法，希尔排序(应该比插入排序运行得更快)尝试通过不同的 h 排序来最小化反转距离。 在某种程度上，这个 h 排序过程使文件几乎排序，从而以更对称的方式重新排列反转分布。

那么怎么能说(根据书)插入排序的运行时间取决于反转的数量而不是它们的分布方式？

Answer 1

在插入排序中，每进行一次交换都会将反转次数减少一倍。例如，想象一下，我们要在插入排序中交换两个相邻元素 B 和 A。在交换之前，数组看起来像这样:

   +--------------+---+---+------------+
   |    before    | B | A |    after   |
   +--------------+---+---+------------+

然后，它看起来像这样:

   +--------------+---+---+------------+
   |    before    | A | B |    after   |
   +--------------+---+---+------------+

现在，考虑一下数组中的反转。纯粹“之前”或“之后”的任何反转仍然存在。从“之前”到“之后”的每一个倒置仍然存在，就像从“之前”到A、“之前”到B、A到“之后”以及B到“之后”的倒置一样。唯一消失的反转是特定的反转对 (A, B)。因此，插入排序中的交换次数恰好等于反转次数，因为每次反转都需要一次交换，并且当没有剩余反转时算法将停止。请注意，重要的只是反转的总数，而不是反转的位置。

另一方面，对于 shellsort 来说，这不是。假设在 shellsort 中我们交换元素 B 和 A，它们不在位置但不相邻。示意性地，在交换之前我们有这样的东西:

   +--------------+---+----------+---+------------+
   |    before    | B |  middle  | A |    after   |
   +--------------+---+----------+---+------------+

我们以此结束:

   +--------------+---+----------+---+------------+
   |    before    | A |  middle  | B |    after   |
   +--------------+---+----------+---+------------+

反转 (B, A) 现在已经消失，但也很可能通过此步骤消除了更多反转。例如，假设“middle”中有一堆小于 B 的元素。那么单次交换就会同时消除所有这些元素。

因为 shellsort 中的每次交换都可能消除多个反转，所以这些反转的实际位置实际上对运行时很重要，而不仅仅是它们的位置。