问题标签 [shellsort]

我之前问过这个问题，但是我的帖子里堆满了一大堆其他代码并且没有清楚地呈现出来，所以我要再试一次。对不起，我是新来的

壳牌排序，我是怎么写的，只在某些时候有效。Arraya是一个包含 100 个未排序整数inc的数组，是一个由 4 个整数组成的数组，其值是 shell 排序应该使用的间隔（它们下降并且最终值始终为 1），count是一个存储不同运行 shell 排序的计数的数组,cnt表示应该为此运行的 shell 排序更新的计数值。

当我以不同的 4 个间隔多次运行 shell 排序时，只有有时排序才能完全工作。一半时间数组完全排序，另一半时间数组部分排序。

任何人都可以帮忙吗？提前致谢！

首先，这是我的 Shell 排序代码（使用 Java）：

这是 Shell 排序的正确实现吗（暂时忘记最有效的间隙序列 - 例如，1,3,7,21...）？我问是因为我听说 Shell 排序的最佳情况时间复杂度是 O(n)。（参见http://en.wikipedia.org/wiki/Sorting_algorithm）。我看不到我的代码实现了这种效率水平。如果我向其中添加启发式方法，那么是的，但就目前而言，没有。

话虽如此，我现在的主要问题是 - 我很难为我的 Shell 排序实现计算 Big O 时间复杂度。我确定最外层循环为 O(log n)，中间循环为 O(n)，最内层循环也为 O(n)，但我意识到内部两个循环实际上不是 O( n) - 他们会比这少得多 - 他们应该是什么？因为显然这个算法比 O((log n) n^2) 运行效率更高。

非常感谢任何指导，因为我很迷茫！:P

我正在编写排序算法——Shellsort。错误在哪里？

有没有办法计算 for 循环的起点及其调整。原始循环有这些条件

for( int gap = a.length / 2; gap > 0; gap /= 2 )

我对其进行了调整以设置 Hibbard's Shell Sort 的条件并得到了这个

for( int gap = (int) Math.pow(2, a.length); gap > 0; gap /= 2 )

它工作得稍微好一点，甚至可能是正确的，但我想从这里开始使用更高级的 shell 类型。

http://en.wikipedia.org/wiki/Shellsort#Gap_sequences

如何将 (3^k - 1)/2 不大于 n/3 的上限转换为 for 循环条件？

我的 shell 排序实现的时间复杂度是多少？

我有一个 Java 代码，它运行良好，但是转换为 JavaScript 的代码会引发错误。ShellSort 方法将一个数组传递给该方法。（我正在使用控制台进行调试）我的代码是：

捕获的错误是-- [13:52:59.581] ReferenceError: reference to undefined property nums[(j - h)] @ file:///C:/Documents%20and%20Settings/erickribeiro/Desktop/www/index.html:240

测试页面：dev.erickribeiro.com.br/index.html

完整的脚本是 html 页面。怎么了？

我的程序的一小部分有问题，它制作了一个随机数列表，然后 shell 对它们进行排序，现在它不会完成计算，这让我认为循环没有完成。我遇到了分段错误错误，但我设法通过解决我访问数组的一些问题来解决这个问题。无论如何，一双新鲜的眼睛可能对我有好处。

谢谢！

这是维基百科页面中的伪代码。我不确定我的 c++ 代码是否正确。这是我的代码：

这是我的测试代码：

但它在屏幕上什么也没显示。

我在这样的应用程序中实现了 shell 排序算法：

问题是这样的：

1. 排序的第一部分仅突出显示 '21'，它不能突出显示，因为 15 和 21 没有从条目中改变它的位置.. 列表条目是 15,14,0,34,2,44,21,6 ,7,12,5,34,20。

如果索引 0 大于索引 7，即列表总数的一半 + 1，它们将改变位置，

这是配对：

第一次迭代：15-21、14-6、0-7、34-12、2-5、44-34、6-20

我要强调的是那些只有位置发生变化的人。

我的错误是什么。

我有两种不同类型的两种实现，InsertionSort 和 ShellSort。

它们如下：

插入排序：

贝壳排序：

我还有 10 个包含 32000 个整数的整数数组。我得到了在这些类中调用静态 sortArray 方法之前的时间。结果如下：

对于 InsertionSort.sortArray：

对于 ShellSort：

那么他们之间怎么会有这么大的区别呢？它们基本上是相同的算法？

此外，ShellSort 的前 2 次运行怎么可能需要更长的时间，但其余的运行速度更快？

这是 128000 个元素的结果，再次先进行 InsertionSort：

贝壳排序：

我确信我传递给方法的数组是完全相同的，而且它们是非常随机的。