您将得到n个不同宽度的瓶子和n个不同宽度的盖子的集合，您需要找到哪个盖子与哪个瓶子一起使用。您可以将盖子与瓶子进行比较，从中可以确定盖子是大于瓶子，小于瓶子还是正确的大小。但是，无法将瓶子或盖子直接相互比较，即无法将盖子与盖子或瓶子与瓶子进行比较。设计一个平均问题效率为Θ（nlogn）的算法。
所以我们有两个大小为n的数组。我有点不知道如何解决这个问题。我正在考虑使用另一个数组中的最终变量作为枢轴，对每个数组进行快速排序。B =（1,3,5,2）L =（2,1,5,3）因此，以L中的3作为我的支点，我将对Bottle数组运行quicksort直到其升序。 B =（1,2,3,5）然后我将翻转到L，然后使用B中的5作为我的枢轴并运行quicksort，直到L也以升序排列。
我不确定我的想法是否正确，还是什至是O（nlogn）。
任何帮助将不胜感激。
快速排序都列出了通常的方法。 Quicksort本质上是O(n log n)平均。执行精确两次会将运行时乘以constant因子。产生的复杂性是
O(n log n) * O(1) = O(n log n)
所以复杂度类不会改变。
如果可以使用瓶子的选择来选择更好的枢轴，请继续，但这只是一种启发，不会影响问题的复杂性。