仅使用可以排序n个数字的函数对n ^ 2个数字进行排序

Question

有一个函数F()可以对任何n个数字进行排序,现在有n ^ 2个数字需要排序,至少需要多少次调用F()？(你只能调用F()).我想出了一个像冒泡排序的方法,大概是O(n ^ 2)次调用.有更好的方法吗？

Answer 1

零。您可以编写一个对n^2数字进行排序的新函数，并且不需要调用F(). 这是作弊吗？我不这么认为。这完全取决于除了打电话之外您还可以做什么F()。

您可以将n^2号码划分为号码n组n并调用F()每个组，然后对号码n列表进行合并n。这也是一个看似合理的解决方案，但您可能仍然称其为作弊。

如果你想进一步对问题施加约束，可以有更具体的解决方案，但你必须明确地阐明这些约束。