有一个函数 F() 可以对任意 n 个数字进行排序，现在有 n^2 个数字需要排序，你至少需要调用 F() 多少次？ (您只能调用 F() )。 我想到了一种类似冒泡排序的方法，大约O(n^2)次调用。有什么更好的办法吗？
最佳答案
您将需要 n(2n-1) 步(最坏情况)。这是一个直观的解释:
假设有 4 个排序组，每个组的大小为 (n/2)。我们称它们为 A、B、C、D。 还假设这些组中的每一个都已排序，初始输入向量为 DCBA，最终排序向量应为 ABCD。
在每个单独的操作中，我们可以更改 2 个组的顺序(例如，将 BA 更改为 AB)。
排序 DCBA 需要以下步骤:
DCBA --> CDAB(2 步)--> CADB(1 步)--> ACBD(2 步)--> ABCD(1 步)
总步数:6 = 4*3/2
现在支持您需要对 FEDCBA 进行排序:
FEDCBA --> EFCDAB(3 步)--> ECFADB(2 步)--> CEAFBD(3 步)--> CAEBFD(2 步)--> ACBEDF(3 步)--> ABCDEF(2步骤)
总步数:15 = 6*5/2
等等....
要对每个大小为 (n/2) 的 x block 进行排序，您需要 x(x-1)/2 个步骤(每个步骤对 n 个连续元素进行排序)。
n² 个元素是 2n * (n/2) 个 block ，因此您需要 (2n)(2n-1)/2 = n(2n-1) 个步骤。
编辑:
如果单个 n 排序器 (F) 可以对任意元素(不一定是连续的)进行排序怎么办？
这是一个与 sorting networks 相关的研究级问题.另见 here .
看看这个recent paper by Shi, Yan, and Wagh :
In this work, we propose an n-way merging algorithm, which generalizes the odd-even merge by using n-sorters as basic building blocks, where n (≥ 2) is prime. Based on this merging algorithm, we also propose a sorting algorithm. For N = n^p input values, p + ⌈n/2⌉ × p(p−1)/2 stages are needed. The complexity of the sorting network is evaluated by the total number of n-sorters. The closed form expression for the number of sorters is also derived.
关于algorithm - 仅使用可以对 n 个数字进行排序的函数对 n^2 个数字进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31134625/