arrays - 我们如何根据运行时性能在两种排序算法之间切换？

Question

我正在尝试编写一个程序，它将输入数组作为输入并对它进行排序。排序将是这样的:

程序将开始使用下面提到的任何排序算法对数组的前 20% 进行排序。如果在 20% 之后，程序确定排序算法正在使用最坏情况时间，程序将切换到其他排序算法并继续使用该排序算法对数组进行排序。我在这里面临的问题是如何知道排序算法是否在最坏情况下花费时间？

我将使用的排序算法是:

快速排序，合并排序，桶排序

我们将不胜感激。

Answer 1

“对数组的前 20% 进行排序”是什么意思？

我认为无论您指的是什么，都需要首先对数组进行排序，以便您可以检查数组的排序程度。那么如何在不必先对数组进行排序的情况下得出排序后的版本呢？这就像先有鸡还是先有蛋的问题。

回到您的主要问题，据我所知，大多数排序算法的运行时复杂度都是根据复制操作的数量来分析的。例如，插入排序需要很多复制操作，因为当你需要在正确的位置插入一个元素时，你必须移动元素。其他算法根据swap操作的个数来分析，也可以分解为3个copy操作。

但是，正如我上面提到的，我不知道如何将数组定义为 x% 排序，也不知道在没有排序数组的情况下如何衡量这种排序程度。