用于计算数组中所有元素的顺序的快速算法？

假设给出了一个由一些完全有序集合中抽取的n个不同元素的数组A.例如，也可能会提供用于计算数组中所有元素的顺序的快速算法？

137 13 7 42 38

的目标是产生用于此的数组元素的匹配阵列乙使得B [i]为，比A小原始数组中元素的数目[I的]。例如，在上述阵列中，我们会想产生

A = 137 13 7 42 38 
B = 4 1 0 3 2

由于137是其他大于四个元件（13，7，42，38），13只比元件中的一个（7大），7大于没有其他元素等。

在最常见的情况下，数组中的元素是只能比较的任意对象，任何解决此问题的方法都必须在Ω（n lg n ），因为一旦我们有了这个表，我们就可以在O（n）时间内对数组进行排序，方法是创建一个新的n个元素数组，然后将每个元素放在表中指定的位置。但是，我不知道的是，如果元素不是任意值，我们可以构造这张表的速度有多快。

我的问题是这样的：假设给出了一个n个不同的数组整数值，并且想要为该数组构建一个顺序统计表。什么是最有效的算法？如果有帮助，你可以假设整数为正，并且其中最大的有值U

目前，我有最好的复杂度为O（N LG N）解决方案，它通过使阵列的复制工作，对它进行排序，然后对原始数组中的每个整数进行二进制搜索以在新数组中找到它的位置。这是一个很好的解决方案，但我真的希望能有更好的方式来做到这一点。

来源

2011-03-17 templatetypedef

不是一个完整的回答，但是你可以使用http://en.wikipedia.org/wiki/Radix_sort这是整数O（kN）。 – eulerfx 2011-03-17 20:32:03

@ eulerfx- IIRC基数排序在O（n lg U）中运行，其中U是您正在排序的最大整数。我相信如果你使用van Emde Boas树，你可以把它降到O（n lg lg U），尽管常数因子可能要高很多。 – templatetypedef 2011-03-17 20:51:19

步骤1：数组索引。

A = 137 13 7 42 38 
I = 0 1 2 3 4 

A' = 7 13 38 42 137 
I' = 2 1 4 3 0

步骤2：每I'[i] = j分配B[j] = i。

I' = 2 1 4 3 0 
i = 0 1 2 3 4 

B = 4 1 0 3 2

来源

2011-03-17 20:37:12 aaz

+1这是一个**很棒的**解决方案。我没有想到保持原始指数。 – templatetypedef 2011-03-17 20:40:04

你打败了我。 – AShelly 2011-03-17 20:42:19

奇怪的是第2步与第1步完全一样的索引排序操作，但可以在O（n）中作为鸽子排序完成。 – aaz 2011-03-17 20:52:28

最有可能你想有n^2-N是第一组的所有组合，然后每个元素比较其它找到第一位数字，并用第2个数组的第一个阵列的每个数字重复此计数。

来源

2011-03-17 20:32:46 Bytemain

这会工作，但它是O（n^2），我已经有了一个在O（n lg n）中工作的一般方法，即使输入不是整数。 – templatetypedef 2011-03-17 20:37:57

请停止恳求upvotes。如果你的答案值得赞赏，你会得到它。问他们只是噪音，看起来非常糟糕。 – 2011-04-01 02:41:50

@Ken：你能解释一下为什么它看起来不好？你不是用来乞讨吗？我从哪里来，我求求你了！ – Bytemain 2011-04-01 03:12:20

这个问题至少没有比较的方法比O（n log n）好，这是一个普通的lower bound for comparison-based sorting。（否则你可以应用新的魔法过程，然后迭代B来构造A的排序版本）。

但是，如果输入数组A的整数限制在某个已知范围内，比如说[1..M]，那么可以通过标记这些数字来做更好的事情 - 即O（M + n） - ，例如L [1..M]），它们出现在A中，记住它们在A中的位置并且随后从索引1..M到构造B通过L来扫描。

来源

2011-03-17 20:34:51 dcn

这是事实，但这是一种指数时间算法（因为M在输入中的log M位中表示）。我希望得到输入大小的多项式。 – templatetypedef 2011-03-17 20:37:17

当然，只有M = o（n log n）才有帮助。否则，排序就是这么做的。 – dcn 2011-03-17 20:41:43

这并不完善的大O，但是你的算法做2个不同的N- LOGN操作。排序一个{value, originalIndex}结构数组，而不是排序数组本身。

然后通过排序后的数组做rank[sorted[i].originalIndex]=i;

这仅是1的N- LOGN操作行走。

并与结合U上一个最大，你可以做一个基数排序得到O（千牛），而不是（假设你有内存）

来源

2011-03-17 20:41:36 AShelly

一种方法做它用prefix sums

来源

2011-03-17 20:57:56 fabrizioM

@ fabrizioM-此链接似乎已损坏;你可以发布不同的链接吗？ – templatetypedef 2011-03-17 21:07:06

固定链接，签出postscript文件。 – fabrizioM 2011-03-17 21:24:32

此外，这种方式是高度可并行化的，并且是GPU解决方案的工作原理 – fabrizioM 2011-03-17 21:26:10

用于计算数组中所有元素的顺序的快速算法？

回答

相关问题