有一个外部整数数组，您可以在 O(1) 时间内对其执行以下操作。
反向示例：考虑一个数组 {1,2,3,4,5}。reverse(0,2) 将返回 {3,2,1,4,5}，reverse(1,4) 将返回 {1,5,4,3,2}。
编写代码对外部数组进行排序。提及您的代码的时间和空间复杂度。
显然我们可以使用快速排序或归并排序在 nlogn 中进行排序。但是考虑到风景，我们能做得更好吗？
对数组进行排序就是找到将其恢复到排序状态的排列或洗牌。换句话说，您的算法确定n!必须应用哪些可能的排列，并应用它。由于您的算法通过询问是 - 否问题（是 celli小于还是大于 cell j？）来探索数组，所以它遵循具有 depth 的隐式决策树log(n!) ~ n*log(n)。
这意味着将O(n*log(n))调用以get()确定如何对数组进行排序。
一个有趣的变体是确定对reverse()数组进行排序所需的最小调用次数，一旦你知道你需要什么排列。我们知道这个数小于n-1，可以通过选择排序来实现。最坏情况数可以小于n-2吗？我必须说我不知道...
我会尝试将问题简化为基于经典swaps()的排序算法。
在下文中，我们假设不失一般性j>=i：
请注意，swap(i,j) = reverse(i,j)对于每个j <= i+2，反向子数组仅在有 3 个或更少元素时交换边
现在，对于任何j>i+2- 您只需要reverse()数组，通过交换边 -然后反转“中间”以使其恢复原始状态，因此您得到：swap(i,j) = reverse(i,j) ; reverse(i+1,j-1)
使用刚刚构建的swap()，您可以使用任何使用交换的基于比较的算法，例如快速排序，即O(nlogn). 复杂性仍然存在O(nlogn)，因为每个操作swap()最多需要 2 个reverse()操作，即O(1)
编辑：注意：这个解决方案适合原始问题（在编辑之前），它要求一个解决方案，而不是比快速排序/合并排序更好地优化它。
假设您想最小化外部操作的数量get并且reverse：
get通过调用n 次将所有整数读入内部数组reverse通过最多调用 n 次对外部数组进行排序这具有 O(n) 时间和 O(n) 空间复杂度。
编辑以回应匿名反对票：在谈论时间复杂度时，您总是必须说明要计算哪些操作。在这里我假设，只有外部操作有成本。
基于get(int i)和reverse(int i, int j)，我们无法优化代码。它将具有相同的复杂性。