0

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

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

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

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

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()]),
[...]
4

1 回答 1

1

因为一次通过是应用间隙序列的一个元素，所以通过次数取决于使用的间隙序列。

如果您使用 Shell 的原始间隙序列的 2 次幂，则通过次数大约是输入大小的二进制对数。

您可以在关于 Shell Sort 的维基百科文章中阅读有关其他建议的间隙序列的更多信息：https ://en.wikipedia.org/wiki/Shellsort

于 2020-06-18T15:22:30.667 回答