2012-04-24 151 views
1

假设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排序来完成这项工作吗?

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

回答

1

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

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

+0

阿哈,当再次想到时,它真的不难〜 – Gnijuohz 2012-04-24 02:33:36

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

相关问题