我正在尝试编写一个程序，将输入数组作为输入并将其排序。排序将像这样:
程序将使用下面提到的任何排序算法开始对数组的前20%进行排序。如果在20%之后，程序识别出排序算法占用了最坏情况的时间，则程序将切换到其他排序算法，并使用该排序算法继续对数组进行排序。我在这里面临的问题是如何知道排序算法是否在最坏情况下花费时间?
我将使用的排序算法是:
快速排序,归并排序,存储桶排序
数组的"前20%排序"是什么意思?
我认为无论你的意思是什么，都需要先有一个数组的排序版本，这样你就可以检查数组的排序程度。那么如何在不先对数组进行排序的情况下得到排序后的结果呢?这就像鸡生蛋还是蛋生鸡的问题。
回到你的主要问题，据我所知，大多数排序算法的运行时复杂性是基于复制操作的数量来分析的。例如，插入排序需要许多复制操作，因为当您需要在正确的位置插入元素时，您必须移动元素。其他算法是根据交换操作的数量来分析的，交换操作也可以分解为3个拷贝操作。
但是，正如我上面提到的，我不知道如何将数组定义为x%排序，也不知道如何在没有排序数组的情况下测量这种排序级别。
使用堆排序最坏情况下的时间复杂度nlogn和常数空间。
首先，快速排序是数组的首选算法，而归并排序是列表的首选算法，主要是因为归并排序需要O(N)额外内存。
你的问题的一个解决方案可能是首先做快速排序，然后每次分割你首先检查你的部分数组中有多少不同的元素。如果这个数字相对较小，则执行桶排序，否则继续快速排序。
为了找到阈值，您可以制作一个大型的测试集，其中包含不同长度和分布的随机数组，并比较快速排序和桶排序的性能。在制作测试数组时，尽量模拟您的使用场景。这样，您可以在一定程度上错误地确定数组中不同元素数量的阈值。
在大多数情况下，我使用阈值~1000个不同的元素，但是这非常依赖于您的使用场景，所以执行测试是最好的选择。