1

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

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

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

List<Color> colors = [
    Color(0xFFFF0000),//red
    Color(0xFFFF5500),
    Color(0xFFFFAA00),
    Color(0xFFFFFF00),//yellow
    Color(0xFFAAFF00),
    Color(0xFF00FF00),
    Color(0xFF00FF00),//green
  ];
[...]
style: TextStyle(
    color: colors[(((pass - 1) * (colors.length - 1)) / sqrt(a.length).ceil()).floor()]
),
[...]

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

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

color: colors[(((pass - 1) * (colors.length - 1)) / (log(a.length) / log(2)).floor()).floor()]),
4

1 回答 1

0

在许多类型的排序中你走了多远通常取决于要排序的元素的初始顺序。对于 shellsort，您有单独的传递，使确定过程进一步复杂化。

作为示例并说明问题，请采用插入排序：

  • 这是在一组特定情况下最快的排序，即对已经按预期方向排序的向量进行排序 - 需要 n-1 比较。
  • 它是相反情况下最慢的一种，对已经排序但方向相反的向量进行排序 - 需要 (n*(n-1))/2 比较

假设 n=100，最好的情况是 99 和最差的 4950 比较。这是所需比较次数的 1:50 倍。因此，当您进行了 50 次比较时，您在最佳情况下的结果为 50%，在最坏情况下的结果为 1%。

Shellsort 对于已经排序的数据没有插入排序那么好的案例，但它仍然非常好。相反的情况——插入排序的最坏情况——实际上并不是 shellsort 的最坏情况，它比插入排序快得多。Shellsort 的最坏情况也比插入排序最坏的情况好得多。这意味着对于给定的 n，您将确切地知道插入排序的最佳和最坏情况，并且您将知道 shellsort 在最好的情况下会稍微慢一些，并且比最坏的情况要快得多 - 如果这有助于您的探索。

但是，无论您怎么看，您都无法可靠地预测您在（shell）排序中的进度，除非您知道特定数据需要进行多少次比较，并且您只有在对它进行排序后才知道。

也许你应该使用微软在 Windows 中使用的进度条：它开始非常快，但突然意识到它已经完成了一半，也许它应该放慢速度以免到达终点，即使还有很多排序仍然存在。在某些情况下，它最后几毫米的行程可能需要几分钟。

于 2021-10-23T18:24:48.887 回答