2

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

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

4

2 回答 2

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）现在已经消失了，但也很有可能通过这一步消除了更多的反转。例如，假设“中间”中有一堆小于 B 的元素。然后，单个交换将同时消除所有这些元素。

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

于 2015-08-26T22:06:06.113 回答
1

本身不是一个答案：shell 排序实际上确实需要比插入排序和可能所有其他排序算法更少的平均比较，前提是您为它提供正确的间隙序列，而间隙序列又是 n 的函数（要排序）。每个 n 可能只有一个（唯一的）最佳间隙序列。

当然，定义 F(n) 是棘手的部分！

于 2016-06-27T08:50:42.013 回答