问题标签 [shellsort]

我正在尝试在 Node.js 上编写 shellsort，就像在 Algorithms, 4th ed 一书中一样。塞奇威克，韦恩。那里有所有用 Java 编写的示例。

这是我的模块：

我使用 mocha 和 chai 来测试这个功能：

和外壳排序不起作用：摩卡测试屏幕截图

我正在尝试实现 Shell 排序。了解 Shell Sort 将排序分解为分段插入，我使用值 10 首先除以 5 来开始第一个分段。然后 2 表示第二次分段，然后 1 表示最后一次分段。问题在于 1 的最后一个分段。 if 语句没有检查数组的第一个元素。当使用大小为 12 的数组时，array[0] 和 array[10-11] 发现自己没有排序。我似乎无法在分段插入排序中为我的 for 循环或 while 循环找到正确的起点。10 个未排序的数组：10 9 8 7 6 5 4 3 2 1 已排序：10 1 2 3 4 5 6 7 8 9 12 个未排序的数组：12 11 10 9 8 7 6 5 4 3 2 1 已排序：12 1 2 3 4 5 6 7 8 9 10 11 编辑:: 我认为问题不在于分割方面。将排序的最终段间隙视为 1。 n = size; h = 段；

我需要在 C 中实现 Shell 排序并使用优化版本（首先将间隙设置为 array/2 的大小，然后将该数字重复除以 2.2）。问题是答案并不总是完全排序，我不确定这是因为我的代码中的一些逻辑错误还是 Shell 排序的一些缺点。

这是我的代码：

以下是我的输出：

编辑：在我完成我的问题之前发布

我正在使用 shellsort 从输入文件中查找人口。

这是我的代码：

我在第 33 行收到错误：temp=countryArray[ i ].substring(50,high);

如果我将 50 更改为 0，它可以工作，但我需要从点 50 开始。为什么会出现此错误？

在我的教科书Algorithms中，我读到：

没有关于随机排序输入的 shellsort 的平均比较次数的数学结果。已经设计了增量序列，驱动最坏情况下比较数的渐近增长到 N 4/3、N 5/4、N 6/5、...。. . , 但其中许多结果主要具有学术兴趣，因为对于 N 的实际值，这些函数很难相互区分（以及与 N 的常数因子）。

而且，在bigocheatsheet.com中，Shell 的时间复杂度排序为：

• 最坏的情况下 ：O((nlog(n))^2)
• 平均 ：O((nlog(n))^2)
• 最好的情况： O(n)

而且，这是我对 shell 排序的实现：

现在的问题是，我无法理解 Shell 排序的最坏情况复杂性是如何产生的 O((nlog(n))^2)。如果我做错了什么，请纠正我。

根据维基百科的文章，我正在尝试使用经验派生的增量来实现 Shell 排序以执行 h 排序：

目前，我正在使用h = 3*h + 1执行排序，这是我的实现：

现在，这很好地完成了任务。但问题是，如果我要通过使用经验派生的序列来执行 h 排序来实现 shell 排序，我应该如何根据数组的大小选择我必须使用的增量？

我在 C 中实现了 Shell 排序，它只比冒泡排序快 3 倍。这是我的排序持续时间（以秒为单位）：

这是正常的还是我的实施可能有问题？

如果我使用 shell 的间隙并始终降低 gap=n/2 我怎么能简单地得到复杂性背后的数学。我知道并阅读了这里的所有其他问题，但对我来说似乎并不明显。

到目前为止我得到了什么：

对于shell（1之前的每个间隙，所以在插入排序开始之前）我们有

对于插入排序，我们有

这一起意味着：

所以这一起意味着我有最坏的情况 O(n^2)？

到目前为止是正确的吗？

我怎样才能证明这一点？

这是作业的一部分，我们必须在其中比较不同的排序算法。为了进行公正的测试，我应用了一些基本的统计概念。我没有运行单个测试，而是执行了具有不同数组大小的测试样本。样本量是固定的，100，每轮的元素数量不等：一千、一万、十万、一百万和一千万个元素，数组是随机填充的。

由于插入排序的限制，十万个元素后没有测试。还记录了每个算法执行的比较次数和数组访问次数。

在报告的最后，shell 排序优于堆排序。我不清楚原因。可能与填充数组的方式（使用随机数）有关吗？

这是用于两种算法的代码：

我对编码还很陌生，我一直在努力处理这段代码，它允许我随机生成大量整数数组，选择特定的 shell 排序，然后测试数组是否正确排序。

我不知道我做错了什么，shell排序实际上并没有对数组进行排序，或者至少它没有进行降序排序，如果程序确实检查以确保数组正确排序，它会赢'不显示我希望它显示的消息。