部分排序其中某些數字已排序的數組

Question

我必須按降序對數組進行部分排序，其中某些數字可能已排序。

是他們的任何功能，可以有效地做到或任何有效的算法。

Answer 1

Timsort是專門爲這種情況設計的。

Timsort是混合排序算法，從合併排序和 插入排序衍生，設計成多種真實世界 數據的表現良好。它是由Tim Peters於2002年發明的，用於編程語言Python 。該算法找到已經排序的數據的子集，並使用子集高效地對數據進行排序。

另一種替代方案是Smoothsort，也被設計爲利用部分排序的數據。

它是由Edsger Dijkstra算法在1981年 像堆排序開發的堆排序的變化，smoothsort的上限爲O（ñ日誌ñ）。該 優勢smoothsort的是，它更接近於O（ñ）如果 輸入已經被分類到一定程度的時候，而堆排序平均 O（ñ日誌ñ）不管初始排序的狀態。

Answer 2

std::sort一般。

雖然確切的實施細節是實施的質量，但良好的std::sort實施應該利用數據的部分排序性質。例如，libc++。

請注意，如果您知道排序的部分在哪裏，則可以使用std::inplace_merge。例如，假設v是vector，其中[1,7]被排序並且[7,10]也被排序，則可以使用std::inplace_merge(v.begin() + 1, v.begin() + 7, v.begin() + 10)，但是這更容易出錯。

至於結果的順序：如果<不適合你，隨意提供自己的比較功能。

Answer 3

如果你在一個循環內進行排序，可以考慮一個treap或紅黑樹。 Treaps平均速度很快（但標準偏差較大），紅黑樹的運行時間變化較小（平均運行時間不夠好，但運行時間標準偏差較低）。 IOW，對於批量應用程序使用樹枝，對於交互式應用程序，您可能需要紅黑樹，以便用戶不必等待很長時間。

如果你不是在一個循環中排序，然後Timsort。