預排序分析算法？

這是一個衆所周知的與Quicksort isssue，當數據集處於或幾乎排序，性能下降可怕。在這種情況下，Insertion Sort（通常非常緩慢）很容易成爲最佳選擇。問題是知道何時使用哪個。預排序分析算法？

是否有算法可用於運行數據集，應用比較因子並返回數據集按照排序順序接近的報告？我更喜歡Delphi/Pascal，但如果示例不是太複雜，我可以閱讀其他語言。

2009-12-04 Mason Wheeler

如果實現對於選擇元素元素來說太簡單，那麼使用預排序序列的快速排序的緩慢性只是一個問題，AFAIK。例如，請參閱http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html。 – Dirk 2009-12-04 20:06:41

正如您所期望的那樣，我們有很多想法。三中位數技術意味着排序數據不會出現快速排序的最壞情況行爲，而是出現不太明顯的情況。

Introsort是相當令人興奮的，因爲它完全避免了quicksort的二次最壞情況。與其自然而然的問題不同，「我如何檢測數據幾乎被排序」，它實際上是在問自己是否正在進行，「這是否花了太長時間？」。如果答案是肯定的，它會從快速排序切換到堆排序。

Timsort將合併排序與插入排序組合在一起，並且對排序或反向排序數據以及包含排序或反排序子集的數據執行得非常好。

所以你的問題的答案可能是「你不需要預分析，你需要一個自適應排序算法」。

來源

2009-12-04 20:49:42

+1 timsort鏈接 – 2009-12-04 21:10:45

+1哇，timsort看起來很整潔。 – wowest 2009-12-04 21:28:25

我還沒有聽說過任何預分揀分析，但我的觀點是，如果你要通過數據集來分析它，那麼你已經在削減整體分揀時間的表現。

來源

2009-12-04 20:07:22 martinatime

這是一個很好的觀點，但如果分析過程是O（n），它將不會支配漸近分類時間。如果它可以幫助避免O（n^2）最差情況下的排序時間，那麼對於大型數據集的排序時間可能是一個淨效益。 – ddaa 2009-12-04 20:14:07

@ddaa：對於比較排序，這是正確的，但是使用基數排序或排序排序可以進行O（n）排序。如果我們包含這些算法，排序時間可能會受到分析時間的支配...... – 2009-12-04 20:28:48

@Jason：您不會對您即將進行排序的數據執行此分析。問題是關於快速排序和插入排序之間的選擇，並且你打算不這樣做...... – 2009-12-04 20:59:25

一種可能的解決方案是在當前排序範圍內（QuickSort操作期間）取第一個，最後一個和中間元素，並選擇中間元素作爲主元素。

來源

2009-12-04 20:13:27 gabr

你最好的情況仍然是O（N日誌N），其中插入排序是O（N）幾乎排序的數據。 – wowest 2009-12-04 20:15:13

爲了充分分析決定使用哪種算法的目的，你將要做幾乎排序的工作。你可以做一些事情，比如檢查一小部分隨機但增加的索引值（即分析一小部分項目）。

來源

2009-12-04 20:13:35

還有SmoothSort，這顯然是相當棘手的實現，但它取決於數據的排序方式從O（N log N）到O（N）之間的變化。

http://en.wikipedia.org/wiki/Smoothsort

朗棘手PDF： http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

然而，如果你的數據確實是巨大的，你必須連續訪問它，歸併可能是最好的。它始終是O（N log N），它具有出色的「局部性」屬性。

來源

2009-12-04 20:14:25 wowest

您仍然需要遍歷所有記錄以確定它是否已排序，以便提高性能，從第一條記錄開始並運行，直到您發現某些未正確排序的內容或達到列表。如果您發現錯過，那麼只會將該位置的項目排序到最後（因爲列表的開頭已經排序）。

在第二部分的每個項目中，查看該項目是否爲<，而不是第一部分的最後一個元素，如果是這樣，則僅對第一部分使用插入排序。否則，快速排序第二部分中的所有其他項目。這種方式是針對特定情況進行優化的。

來源

2009-12-04 20:38:25 skamradt

快速排序繃只有當數據集是巨大的，已經大多排序，我會用下面的啓發式（一個完全成熟的解決方案待定）一個問題：

如果數據集大小不要打擾低於閾值。
如果您對記錄（項目）有快速（索引）訪問權限，請在每N條記錄中記錄一條記錄，並查看它們是否已經排序。對於小樣本應該足夠快，然後您可以決定是否使用快速排序。

來源

2009-12-04 20:48:48

但如果每個N中有1條記錄排序，則樣本失敗，但是每N個記錄中的+1記錄不是。您可能仍然需要閱讀每條記錄，看看其中一個未採樣是否出現故障。 – skamradt 2009-12-04 21:40:43

同意，但統計上很少有機會，樣本會偏離整體人羣，尤其是如果你隨機化了一點N. – 2009-12-05 00:34:28

爲了提出人們還沒有做出的概念性觀點：Quicksort是一種常見的分而治之算法，在極少數情況下具有明顯的缺陷。假設你想分類一堆學生論文。（我必須處理一些規律性問題。）在快速排序算法中，您選擇一些紙張，即關鍵點。然後根據是否在數據透視之前或之後劃分其他文件。然後用這兩個子文件重複一遍。什麼是錯誤？關鍵點可能是一個靠近列表的一端而不是中間的名稱，因此將它分成兩堆並不是很成功。

合併排序是另一種分而治之算法，它以不同的順序工作。您可以在線性時間合併兩個排序列表。將論文分成兩個相等或幾乎相等的紙堆，然後遞歸排序，然後合併。合併排序沒有任何錯誤。快速排序比合並排序更受歡迎的一個原因是歷史性的：Quicksort速度很快（通常），而且它沒有任何額外的內存。但是現在，保存比較比保存內存更重要，實際的重新排列通常是通過排列指針來提取的。如果事情總是如此，那麼我懷疑合併排序只會比快速排序更受歡迎。（也許在名稱中加入「quick」是很好的推銷手段。）

來源

2009-12-06 23:00:29

從我的POV中，就地排序的好處並不在於它節省了*內存*，因爲它節省了內存分配，因此不會失敗。所以當對一個數組進行排序時，quicksort/heapsort /插入排序/冒泡排序都具有比mergesort更好的用戶界面。如果mergesort比快速排序更受歡迎，那麼當然你可以嘗試分配內存，如果失敗了，可以改爲快速排序。如果你正在分配一個輔助數組指針並對其進行排序，那麼你正在引入失敗的可能性，因此可能允許在別處失敗。 – 2012-07-09 09:21:26

@SteveJessop這是一個公平的觀點。然而，這種擔憂雖然在某些情況下仍然很重要，但也有些過時。我同意，外部環境公平分配內存給每個需要它的客戶端程序或函數是不平凡的。然而，即使是在很多環境下，這種情況也會隨着時間的推移而變得更好。 – 2012-12-04 15:22:25

我不認爲這是一個真正的公平問題，就像您用完時發生的情況一樣，以及您是否對此感覺強勁。如果分配失敗，那麼你可以單獨編寫程序。如果操作系統將水衝出來，直到它有足夠的內存來滿足第一次訪問請求或頁面錯誤，那麼您可以用另一種方式編寫程序。有些語言會走中間路徑，理論上你可能會發現內存不足的異常並繼續，但在實踐中你不會這樣做，你會讓異常殺死你。我想這可以被認爲是「最新」的方式來做到這一點;-) – 2012-12-04 16:53:23

預排序分析算法？

回答

相關問題