部分排序爲N個未排序組的有效算法

Question

我正在尋找一種有效的算法來執行以下操作：給定N個項目的數組，以某種方式對它進行排序，以便項目以M個相等組進行排序，其中每個組是未排序，但組之間彼此排序（一個組中的所有元素都小於下一個組的任何元素）。

最簡單的方法是對整個數組進行排序。但效率不高，特別是如果組數遠遠小於項目總數（例如，將100萬項分爲5組）。

目前我已經決定使用quickselect算法（具體來說，它是Floyd-Rivest variation）將數組排序爲2個未分類的組，然後將其應用M-1次。一個顯着的改進可能是採用分而治之的方法來快速選擇，首先將數組分成兩組，然後對每一組進行排序等等，直到我們有M組。一種泛化的unordered partial sorting問題。

但我有一種直覺，認爲可能有一種更簡單，更有效的方法解決問題。有什麼我失蹤？有任何想法嗎？我需要在我的RBush JavaScript library（一種高效的R *樹實現）中提高批量插入性能。

Answer 1

這裏是重述的問題。您需要同時查找M-1個排名元素，並使用它們將該數組劃分爲M個未排序的組。

我建議與選擇爲接近中值隨機樞軸標準quickselect開始（做隨機子樣本特技來估計），對於每種情況下將所述陣列分成2和也除以排列表您還需要查找2個元素。繼續進行下去，直到您找到您當前組中找到排名元素的級別。然後切換到快速選擇的Floyd-Rivest變體，以實際找到該元素並將當前組拆分爲2.然後從快速選擇中退出，您可以輕鬆拼湊出所需的M個組。

該方法的預期運行時間爲O(N log(M))，具有相當不錯的常量。我懷疑這比那個好得多。