问题标签 [shellsort]

我们的老师没有教我们如何分析算法的运行时间，然后她想让我们报告一下Shell sort。

我只想知道是否有一种简单的方法可以找到像 shell 排序这样的算法的平均/最佳/最差情况性能。

假设我有一个数组：

我不明白如何使用序列 3 进行 shell 排序：我会简单地这样做吗：

我在哪里将它分成 3 个部分并对各个部分进行排序？然后对 2 次排序后做同样的事情，除了分成两半？这样做的正确方法是什么？有人可以解释一下吗？

我有两种类型的问题——堆和壳。我在 C 中有一些代码，我需要在程序的主体中尝试使用相同的命令（比如当我在 C 中使用“for-loop”时，我也想为 Pascal 使用“for-loop”） . 我尝试过，但排序不像在 C 中那样工作。在 C 中，一切都适用于大小为 40000 的数组。

C 中 ShellSort 的代码，其中参数“n”是数组的大小：

帕斯卡声明

具有相同参数的 Pascal 代码：

C中堆排序的代码：

Pascal 中堆排序的代码：

帕斯卡的输出：

我真的很沮丧。

我正在尝试在链表上实现 Shell 排序。我将原始链表划分为子链表，其中包含关于 shell 排序算法的“k”间隙的节点。我想通过操作“下一个”指针而不是更改其数据字段来对子链表进行排序。所以我有一个sortList函数可以遍历链表并在swapNodes遇到任何无序节点时交换节点。

当我将带有两个元素的无序列表传递给时，sortList我不断丢失列表中的一个节点。例如，我的列表中有 50 和 -84，我将其传递给sortList. 在sortList它们无序的数字之后，它调用swapNodes，但一旦swapNodes终止，结果列表只有 50 个。

我尝试 gdb 并发现当我在swapNodes范围内时，列表会成功排序而不会丢失节点，但是当它终止并返回sortList范围时，headandcurr都只指向 50，并且它们的“下一个”字段为 NULL。

我的职能：

我正在创建一个排序可视化工具，并且已经完成了一些算法：冒泡、选择、插入。我也在尝试实现 shell 排序，但排序在整个数组的 3 次迭代后停止。在此之前，排序过程似乎很好。为什么会这样？我可以看到它停止了，因为我在内循环的每次迭代后更新了图表。这是我的代码：

我用它显示的python写了一个shell排序list index out of range，我没有发现问题

我指的是原始（Donald Shell 的）算法。我正在尝试基于 shell 排序进行主观排序。我已经做了所有的逻辑，它与 shell 排序完全相同，但不是计算机计算什么更大，而是用户主观地确定什么更大。但我想向用户显示一个百分比或其他东西，让用户知道它已经排序了多远。这就是为什么我想找到一种方法来了解它。

获得shell排序通过次数的公式是什么？我注意到这个数字不是固定的，那么最小值和最大值是多少？N和N^2？或者，如果您知道如何以最佳方式显示排序进度，我将不胜感激。

PS：不是比较次数的问题！也与时间复杂度无关。我的问题是关于数组中的通过次数。

我做了这个公式用颜色显示它。但它不适用于正确的范围。

我正在尝试基于 shell 排序进行主观排序。我指的是原始（Donald Shell 的）算法。我已经做了所有的逻辑，它与 shell 排序完全相同，但不是计算机计算什么更大，而是用户主观地确定什么更大。但问题是我想向用户显示一个百分比或其他东西，让用户知道它已经排序了多远。这就是为什么我想找到一种方法来了解它。

我试着在这里问（什么是获得shell排序通过次数的公式？），但也许我上次没有很好地表达自己，他们结束了这个问题。我首先尝试将进度与 shell 排序中数组中的通过次数相关联。但最近，我注意到它不是一个固定的数字。因此，如果您知道如何以最佳方式显示排序进度，我将不胜感激。

我做了这个公式，根据遍数按颜色显示它，这是我能得到的最接近的，但它与颜色列表的最大范围不完全匹配。（Dart/Flutter 中的代码）

我不需要这样做，所以如果您知道如何显示排序的进度，请分享。

编辑：我想我找到了答案！至少对于 shell 排序，它是根据 os 通过数组的数量来工作的。只需将 sqrt(a.length).ceil() 更改为 (log(a.length) / log(2)).floor() 这行：

以下是 Valgrind 的报告：

下面是生成函数：

以下是我的 shellsort 函数：

我在 main 中释放了我的实际数组（不是我的序列）。我很好奇是什么导致了 8 的无效读取大小，因为 valgrind 说没有泄漏。我也很好奇 4 个分配器的来源，因为我只为实际数组和序列数组分配。

在我的 shell 排序代码中，我使用了一个表达式来减少第一个 for 循环，它似乎不起作用，这就是为什么我的循环无限运行，有人可以解释为什么递减表达式不起作用吗？这是代码......