分層次列表進入無序分區

Question

我努力尋找以下問題的一個很好的算法：

• 輸入：n個整數的未排序
• 輸出：P（大致）大小相等的無序列表其中每個列表的最小元素大於列表中的最大元素

目標是對輸出進行分層，以便在p = 3的情況下，例如，我得到3個無序列表的小，中，大數量（按此順序）。

例如：

N = 10，P = 3

• 輸入：[4，1,8，7,9，3，6，0,2，5]
• 輸出：[[1，0,2]，[4，3，6，5]，[8，7,9]]

很顯然，我可以通過簡單地排序，然後分割爲此在O(n*log(n))時間，但我想知道這是否不能在線性時間內完成。我知道QuickSelect運行在預期的O(n)平均情況下，所以我的直覺是這個問題應該可以在O(p*n)時間內解決。

天真地，我想你可以簡單地運行QuickSelect p次，連續找到下一個第k個最小元素，然後對每個元素執行一個基數排序，以便通過原始中標識的p個元素來分割元素步。

所以：

1. 我不知道該算法我概述作品
2. 我不知道它 確實採取O(p*n)
3. 即使是O(p*n)，我不知道 這是一個最佳的複雜性（雖然我懷疑它，因爲它 似乎在p = 1和p = n邊緣情況下工作）
4. 這不是很 優雅

有沒有更好的算法？

謝謝

Answer 1

QuickSelect實際上是一種分區算法，所以在QuickSelecting之後不需要額外的步驟。

讓我們假設我們有一個功能分區（ARR，LO，HI）返回一些k這樣lo <= k < hi和重新排列arr這樣arr[i] <= arr[k]如果i < k和arr[k] <= arr[i]如果k < i。然後，在本質上，QuickSelect是：

# After this call: 
# arr[i] <= arr[med] if lo <= i < med 
# arr[med] <= arr[i] if med < i < hi 
QuickSelect(arr, lo, med, hi): 
    if lo < hi: 
    k = Partition(arr, lo, hi) 
    if med < k: 
     QuickSelect(arr, lo, med, k) 
    else if k < med: 
     QuickSelect(arr, k + 1, med, hi) 

這是非常相似的快速排序：

QuickSort(arr, lo, hi): 
    if lo < hi: 
    k = Partition(arr, lo, hi) 
    QuickSort(arr, lo, k) 
    QuickSort(arr, k + 1, hi) 

由於QuickSelect分割在指定點的數組（不僅僅是找到關元多一點）中，我們可以很容易分層次定義爲QuickSelect重複呼叫：

Stratify(arr, n, p): 
    for i from 0 to p - 2 (inclusive): 
    QuickSelect(arr, floor(i * n/p), floor((i+1) * n /p, n) 

由於QuickSelect是O(n)，上述分層次是O(p*n)。僅對數組進行排序的選項將需要O(n log n)，因此如果p不在O(log n)中，則上面的Stratify非常有用。 （由於log n是一個很小的數字，所以在實踐中很可能是優先排序）。

但是，很容易將分層結合到QuickSelect中，我們可以將它稱爲QuickStratify。 QuickStratify做了快速排序恰好到其中陣列是分層的點：

爲了方便起見，它報告的功能，其地層的給定索引落入：

Stratum(i, n, p): floor(i * p/n) 

目前：

QuickStratify(arr, n, p, lo, hi): 
    if Stratum(lo, n, p) < Stratum(hi, n, p): 
    k = Partition(arr, lo, hi) 
    QuickStratify(arr, n, p, lo, k) 
    QuickStratify(arr, n, p, k + 1, hi) 

我很確定QuickStratify的平均時間爲O(n log p)，但我沒有證明方便，我可能是錯的。

Answer 2

您的算法看起來不錯。我唯一的狡辯是，我不明白你如何執行你所說的「基數類型」。對於每個值x，您需要確定它進入哪個p時隙，並且由於這些時隙似乎沒有非常特殊的結構（與常規基數排序不同，它們對應於某個固定值的倍數）我認爲你需要每個值的O（log p）比較。

假設只使用比較，你不能比O（n log n）做得更好，因爲如果你可以的話，你可以通過設置p = n來分類n個比O（n log n）更好的數字並運行該算法。

另請注意，如果一個值可能出現很多次，則結果子集可能會任意失衡。（如果您在條件中使用嚴格的「大於」，則這種可能性是不可避免的。）

最後，如果最壞情況的性能是一個問題，那麼有一個worst-case linear algorithm for selection。它有一個很大的常數，請注意，如果你的輸入是異常模式或來自潛在的敵對來源，那麼只考慮它。