问题标签 [shellsort]

环境：python3.6、Anaconda 5.1、Jupyter notebook、numba。

我使用Python生成的随机数组来测量shell排序的时间复杂度，但发现它的时间复杂度更符合NlogN。我知道shell排序的时间复杂度是O(n^2)，我很困惑。

外壳排序代码：

shell排序时间复杂度分析

当我对这个数据 {7,8,4,2,3,9,5,8,4,1} 运行排序时，只有第一个元素没有放在正确的位置。我怎样才能解决这个问题？谢谢您的帮助。

我是一名大二学生，正在上数据结构课，今天的课是关于排序算法的。我们学习了选择排序、冒泡排序、插入排序、Shell 排序、快速排序和归并排序（课程按此顺序）。据我所知，Shell 排序的设计和设计比普通的插入排序更快。

所以程序是：

1. 使用 gap 将原始列表分成几个子列表。
2. 使用插入排序对子列表进行排序。
3. 不断减小gap，重复直到gap达到1。

我希望我没有错直到这个级别。如果我是，请告诉我。

如果到目前为止我是对的，我的问题是：

如果这种称为“Shell 排序”的算法被设计并被认为比普通的插入排序更快，那么为什么不在步骤 2 中递归地使用 Shell 排序呢？根据这个逻辑，在对子列表进行排序时使用 Shell 排序而不是插入排序可以加快速度。

我正在编写一个程序来对一组数字执行 shellsort。我首先必须生成将执行 shellsort 的数字序列。此函数用于生成小于要排序的数组长度的 2^p*3^q 形式的数字。然后我对刚刚生成的序列数组进行排序。这是我的实现：

该代码旨在返回一个 long * 数组并将 seq_size 设置为序列数组的长度。例如，如果给定一个包含 16 个整数的数组进行排序，则此处生成的序列数组应该是 8 个整数（1、2、3、4、6、9、8、12）并且 seq_size 应该等于 8。相信我对指针的理解是错误的，因为我的终端输出如下所示：

但是，我不确定如何更改它以使其正常工作。我将此函数称为：

如果我遗漏了任何信息，请告诉我，我非常感谢任何帮助。

我很难理解我的代码是否产生了正确数量的交换（交换）和比较。对于所有三种情况，我得到相同的数字，这与插入排序不同。据我了解，shell 排序是一种改进的插入，它对间隙排序的数字集执行插入排序，这让我怀疑这些值是否正确。

我试过在其他地方计算它们，但我相信我把它们放在正确的地方。我得到的值的唯一区别是当我改变差距时，这显然会改变算法的效率，但这是唯一改变效率的事情吗？还是我的价值观不正确？

我希望随机值集得到不同的结果。我知道间隙序列对其进行了部分排序，但我得到 Exchanges(Swaps) - 10 和比较 - 5 的值，从 1-10 升序、降序和随机值。这让我不敢相信我的价值观是正确的。shell排序是否使插入排序输入不敏感？任何帮助/输入表示赞赏。

我正在编写一个程序，它需要一个数组并使用 shell 排序。问题是我试图展示从开始到结束之间的每一步。因此，当排序发生时，我试图显示每一次传递以及是否应该交换值。这就是我正在做的事情，但我意识到这是令人费解的方式，无论如何都不会起作用。但它让我了解了我的思考过程。我没有包括 shell 排序代码或任何其他部分，因为我不需要这些帮助......

所以我需要帮助的地方就是写这个；我需要一种方法来实现所有可以用于每次传递的 if 语句，然后在每次传递之后实现新数组......我想我需要编写一个循环，当它通过数组时递增值。我也打算实现这个来实现交换的值。我已经实现了 5 个，因为对于这个特定的传递，这是发生交换的地方。

很抱歉，这可能到处都是，我可以在脑海中看到需要做什么，我只是没有达到实际实施它的地步。我会尽我所能得到的帮助！

我正在尝试计算 Shell sort 对数组进行排序所需的比较和交换int[] array = {1,2,3,4,5,6,7,8,9,10}。使用现在的比较计数器 ( comp) 和当前的交换计数器 ( exch)，我得到 22 次比较和零次交换。我相信零交换是正确的，因为它显然是一个排序数组，所以不需要交换。对于 10 个元素的数组，我认为 22 次比较是不正确的。有人可以告诉我这些表达式需要在哪里并解释原因吗？我将不胜感激。

祝大家有美好的一天！我写了Shell排序验证码，但是我无法构建正确的循环不变量。无法正确组合不变量并证明程序的正确性...请帮助我！

根据维基百科页面，

对于任何非负整数 a 和 b，每个 h 排序和 k 排序数组也是 (ah + bk) 排序的

这怎么可能？我看到了另一个问题，它解释了为什么 h 排序的数组在 k 排序之后仍然是 h 排序的，其中 k 小于 h，但它没有解决这个问题。

我被告知要在课堂上展示 Shell Sort，我做到了。我进行了很多研究，只是为了看到他们中的大多数都写了 O(n log n) 以获得最佳情况时间复杂度。然而，在向我的老师展示了这个算法之后：

我的老师马上反驳我说“这个排序算法最多只有n^3”。

她忘了教我们如何获得程序的时间复杂度，所以我在这里迷路了。