用於計算數組中所有元素的順序的快速算法？

假設給出了一個由一些完全有序集合中抽取的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

用於計算數組中所有元素的順序的快速算法？

回答

相關問題