获取外壳排序中通过次数的公式是什么? [英] What is the formula to get the number of passes in a shell sort?

问题描述

我指的是原始的(Donald Shell's)算法.我正在尝试基于shell排序进行主观排序.我已经做出了所有逻辑，它与shell排序完全相同，但是用户不用主观地确定更大的值，而是由计算机来计算更大的值.但我想向用户显示一个百分比或其他信息，以了解排序的距离.这就是为什么我想找到一种了解它的原因.

I'm referring to the original (Donald Shell's) algorithm. I'm trying to make a subjective sort based on shell sort. I already made all the logic, where it is exactly the same as the shell sort, but instead of the computer calculate what is greater, the user determines subjectively what is greater. But I would like to display a percentage or something to the user know how far in the sorting it is already. That's why I want to find a way to know it.

获取壳排序中通过次数的公式是什么?我注意到它的数量不是固定的，那么最小值和最大值是多少? N和N ^ 2?或者，如果您对这是显示排序进度的最佳方式有一个想法，我将不胜感激.

What is the formula to get the number of passes in a shell sort? I noticed it the number is not fixed, so what would be the minimum and maximum? N and N^2? Or maybe if you have an idea of how it is the best way to display the progress of the sorting, I will really appreciate it.

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

PS: It is not about the number of comparisons! Also not about time complexity. My question is about the number of passes in the array.

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

I did this formula displaying it by color. But it doesn't work with the right range.

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

推荐答案

由于一次通过是应用间隙序列的一个元素，因此通过的次数取决于所使用的间隙序列.

Because one pass is the application of one element of the gap sequence, the number of passes depends on the used gap sequence.

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

If you use Shell's original gap sequence of powers of two, the number of passes is approximately the binary logarithms of the input size.

您可以在Shell Sort上的Wikipedia文章中阅读有关其他建议的空位序列的更多信息: https://en.wikipedia.org/wiki/Shellsort

You can read more about other proposed gap sequences in the wikipedia article on Shell Sort: https://en.wikipedia.org/wiki/Shellsort

这篇关于获取外壳排序中通过次数的公式是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！