排序算法與約束陣列

我想要一個算法，排序和O（nlog（logn））時間A陣列。其中對於所有j> = log（n），A [0 ... n-1]具有性質A [i]> = A [i-j]。排序算法與約束陣列

到目前爲止，我曾想過將分區A分成每個logn大小的塊。

那麼我認爲第一個塊會比它之後的塊要小得多？

我想我錯過了它的一部分。

2014-01-29 user3196347

[log（n）-1]可能大於A [log（n）+1]，但它們在不同的塊中，因此第一個塊不會小於其他塊。 – amit

Tree Sort將是一個選項。您從數組的左端開始並將元素傳入樹中。無論何時你的樹有多於log（n）個元素，你都會把最小的元素拿出來，因爲你確定知道所有後續元素都較大，並將其放回到排序後的數組中。這樣樹的大小總是log（n），而樹操作的開銷是log（log（n））。事實上，你只需要操作（1）插入隨機元素和（2）刪除最小的元素，所以你不一定需要一棵樹，但任何種類的priority queue都可以做到這一點。這樣，平均和最差情況下的性能都能滿足您的要求。

來源

2014-01-29 17:25:25 pentadecagon

@amit：你絕對可以使用這個算法對所有'n'元素進行排序。我也認爲這是一個非常好的算法（特別是使用快速prioqueue實現時），並且在實踐中速度非常快，而且非常緩存高效。介意分享你的想法，一個更好的算法來做到這一點？ –

非常好的答案。我在Google面試中被問到這個問題，這是他們正在尋找的答案:)不知道這是否有什麼可說的 –

排序算法與約束陣列

回答

相關問題