algorithm - 如何根据另一个数组对数组进行排序？

Question

假设A={1,2,3,4}，p={36,3,97,19}，使用p作为排序键对A进行排序。你可以得到{2,4,1,3}。

这是《算法导论》一书中的一个例子。它说它可以在nlogn中完成。

谁能给我一些关于如何完成的想法？我的想法是您需要跟踪 p 中的每个元素以找到它的结束位置，例如 p[1] 结束于 p[3] 然后 A[1] 结束于 A[3]。任何人都可以使用合并排序或其他 nlogn 排序来完成这项工作吗？

我是算法新手，发现它有点吓人:(感谢您的帮助。

Answer 1

构造一个索引数组：

i = { 0, 1, 2, 3 }

现在，在您进行排序p时，对索引数组进行相同的更改i。

完成后，您将拥有：

i = { 1, 3, 0, 2 }

对两个数组进行排序最多需要对一个数组进行排序的时间的两倍（实际上，如果您只计算比较，则无需进行任何额外的比较，只需在两个数组中交换数据而不是一个），所以这不会改变整体排序的 Big-O 复杂度，因为O( 2n log n ) = O(n log n).

现在，您可以使用这些索引A在线性时间内构造排序数组，方法是简单地遍历排序索引数组并查找A该索引处的元素。这需要O( n )时间。

整个算法的运行时复杂度是最坏的：O( n + 2n log n ) = O( n log n )

当然，您也可以完全跳过索引数组，并A以相同的方式简单地处理数组，将其沿边排序p。

Answer 2

我认为这并不困难，因为排序算法的复杂性通常是根据所需的比较次数来衡量的，您只需要A根据B. 除了已经需要排序的比较之外，您不需要进行任何比较，B因此复杂性是相同的。

每次移动元素时，只需在两个数组中移动它即可。