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

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

我没有看到这个困难的，因为复杂性一个排序算法的通常在所需的比较的数量来测量，你只需要根据在B元素来更新阵列A元件的位置。除了已经需要对B进行排序以外，您不需要进行任何比较，因此复杂性是相同的。

每次移动元素时，只需将它移动到两个数组中即可完成。

Answer 2

构建索引阵列中。

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排序它。