问如何根据两种排序算法的运行时性能在它们之间进行切换？

EN

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

我认为无论您的意思是什么，都需要先有一个排序的数组版本，以便您可以检查该数组排序了多少。那么，在不先对数组进行排序的情况下，如何得到排序后的版本呢？这就像是鸡和蛋的问题。

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

但是，正如我在上面提到的，我不知道如何将数组定义为x%排序，也不知道如果没有排序的数组，您如何测量这种排序级别。

使用堆排序、最坏情况、时间复杂度、nlogn和常量空间。

首先，快速排序是数组的首选算法，而合并是列表的首选算法，这主要是因为合并排序需要O(N)额外的内存。

问题的一种解决方案可能是首先进行快速排序，然后每次拆分时，首先检查在您所在的数组部分中有多少不同的元素。如果该数字相对较小，则执行number排序，否则继续快速排序。

为了找到阈值，您可以对不同长度和分布的随机数组进行大量测试，并比较快速排序和桶排序的性能。在制作测试阵列时，请尽可能多地模拟您的使用场景。这样，您就可以在一定程度上确定数组中不同元素数量的阈值。

在大多数情况下，我使用了阈值~1000个不同的元素，但是这非常依赖于您的使用场景，所以执行测试是最好的选择。