排序排列的是部分地排序

它增加高達一定程度那麼它開始減小，則增大後減小等特性的陣列。有沒有任何算法可以通過使用部分有序的方法將它分類爲nlog（n）以下的複雜度？

陣列示例= 14,19,34,56,36,22,20,7,45,56,50,32,31,45 .........高達Ñ

由於提前

2010-10-21 peloooo

您可以找到更改/分區點，並在分區對之間執行合併排序。這將利用現有的順序，因爲合併排序通常以成對的元素開始。

編輯只是想弄清楚這裏的複雜性。合併排序是n log（n），其中log（n）與您必須重新分區的次數相關。首先是每一對元素，然後是每對對，等等......直到達到數組的大小。在這種情況下，你有n個具有p個分區的元素，其中p < n，所以我猜測複雜度是p log（p），但我可以糾正。例如合併每對分區，並根據合併後分區數量的一半重複。

來源

2010-10-21 09:27:15

在相似的線條上，我認爲1）注意方向改變的所有點。 2）我們可以很容易地通過反轉來增加遞減順序，對於n個元素依次取O（n）。 3）現在我們有一個數組，每個元素只改變一個方向。 4）注意到這些我們可以應用合併 – peloooo 2010-10-21 09:36:07

任何指向合併排序的樣本實現，高效的內存移動次數和額外的內存？ – Dummy00001 2010-10-21 10:51:20

谷歌合併排序提出了大量的例子。我通常會使用數組，而我的偏好是就地排序並使用迭代而不是遞歸。對於所問的問題，這非常簡單。找到兩個相鄰的正向和反向序列。將它們合併爲一個正向序列。對數組中的所有序列對重複。從數組開始重複，直到沒有更多的序列。就地合併僅涉及將元素從一個序列交換到另一個序列，其中第二個序列上的光標元素小於第一個序列中的元素。 – 2010-10-21 12:14:15

見Topological sorting

來源

2010-10-21 09:30:20 stacker

哦，這已經在這裏提到：http://stackoverflow.com/questions/480640/what-is-the-best-way-to-sort-a-partially-ordered-list – stacker 2010-10-21 09:30:54

的任意序列會等走向上和向下向上和向下再次除非它們已經完全排序（可能用下來開始，當然）。你可以運行序列記錄它改變方向的點，然後合併排序序列（反向讀取反向序列）

一般來說，複雜度是N log N，因爲我們不知道它是如何排序的在此刻。如果排序適中，即方向變化較少，則比較次數會減少。

來源

2010-10-21 09:31:54 CashCow

鑑於開放性問題具體說明數據是部分排序的，我想我們需要量化這個以便從n log（n）移開。最簡單的方法是計算方向上的分區/更改，我們可以將其稱爲p。在這種情況下，複雜度變成p log（p）。如果n與p成比例，例如p = n/K其中K是常數，複雜度在技術上仍然是n log（n），儘管排序會更快。如果p> n/2，則部分排序的數據的先決條件未被滿足。 – 2010-10-21 10:59:03

如果我們知道它的部分排序的性質，那麼我們可以但我們沒有告知這一點。鑑於規範所說的不過是事實上有些地區在上升，而其他地區則在下降，我們對它的分類完全一無所知，任何數據序列都符合規範。因此，或者沒有比O（N log N）更一般的算法，或者如果你非常聰明並且提出了一個算法，那麼你將在歷史中下降，因爲它將是一種通用的排序算法！ – CashCow 2010-10-22 11:18:36

儘管我很喜歡在歷史中走下坡路，但通用O（n）排序已經存在了一段時間，但在很多情況下佔用了太多的空間。對於給出的樣本數據，鴿子分類可以很好地工作，請參閱http://en.wikipedia.org/wiki/Pigeonhole_sort有時您需要尋求關於規格的說明，而不是將其作爲福音。這個問題是根據部分排序的數據提出的，因此我期望在答案中量化和利用這一點， – 2010-11-16 07:34:03

如果您知道數據「幾乎排序」並且設置的大小相當小（例如可以用16位整數索引的數組），那麼Shell可能是您最好的選擇。是的，它具有O（n^2）的基本時間複雜度（其可以通過用於間隙調整的序列減少到O（n * log^2（n））的當前最壞情況），但是在已經排序的集合上，輸入的排序設置爲O（n）的最佳情況，性能提高。使用Sedgewick的間隔大小序列可以在輸入不像您預期的那樣排序的情況下獲得最佳性能。

來源

2010-10-21 10:26:58

Strand Sort可能接近你要找的東西。 O（n sqrt（n）），O（n）最好的情況（已經排序的列表），O（n^2）最差的情況（列表按照相反順序排序）。

分享和享受。

來源

2010-10-21 10:33:32

排序排列的是部分地排序

回答

相關問題