什麼是最好的方法來維護或測量如何良好的排序集合，所以我們可以選擇最佳的排序算法？

Question

受this question

如果我們事先知道如何對集合進行排序，可以選擇使用哪種算法來排序集合。有沒有一種方法可以測量（或保持測量）集合的排序順序？我們可以這樣做嗎？維護或測量排序好的東西的成本不會超過選擇最佳排序算法的好處？

Answer 1

您可以使用採樣：檢查列表中均勻間隔的N個元素，並查看有多少個按順序排列。 （當然，這隻適用於隨機訪問列表，但通常這是您排序的類型。）

對於小N還有一個閾值。如果N很小（例如10），插入排序即使列表沒有排序。 Java對小N進行了這種優化，否則就是合併排序。

Answer 2

一個propsed溶液：

維護操作（插入/缺失）的數目自上次排序進行。這個數字越高，集合可能越未排序。

Answer 3

如果您不知道任何有關集合的事情，那麼嘗試測試其排序的任何時間將遠遠大於您通過選擇最佳排序算法所獲得的節省。

另一方面，如果您要排序所有具有相似排序數量的多個數據集，則可以測量第一個數據集，選擇一個算法，然後將其用於所有後續數據集。

Answer 4

增廣@Doug：

缺失不能榜上無名少排序，所以你不必跟蹤這些。

發生插入時，請與周圍的元素進行比較以確定此插入是否按順序排列。如果是的話，不要增加計數器。如果不是，請增加「未排序」計數器。

也許這是一個懲罰太多（即每插入兩個比較）。你只能做一個比較更模糊的結果？或者我喜歡只計算插入的想法。

Answer 5

您可以測量數據的頻率 - 如果項目之間有很大的變化，那麼數據是高頻率的，表明一個非常隨機的分佈。

如果變化較小，則數據頻率較低 - 表示非隨機分佈。

您還可以使用過濾器來衡量總體趨勢 - 平均趨勢是可測量的向下或向上 - 如果向下，您可能會考慮翻轉整個陣列或使用「反向」數據的排序。

還有其他的測量方法可以幫助您瞭解信號 - 查看信號處理並查看可以收集的信息。

- 亞當

Answer 6

還有就是內省排序這正是這麼做的，有點...

http://ralphunden.net/content/tutorials/a-guide-to-introsort/

Answer 7

好吧，如果集合被定義排序的第一張支票，這將永遠爲你節省大量的時間:)在大多數情況下，不打擾延伸的收集，測試如果是排序在插入/刪除操作期間，如果集合需要排序，則使用按照定義排序的集合。

如果你想擴展一個集合類來跟蹤排序，只是不停指針集合中的元素的單獨排序列表...

最後，爲99.99％的時間，何必呢？只需使用快速排序。如果你的數據集足夠小，以至於快速排序的大O排序的恆定部分將會取代氣泡排序中的節省時間，排序將如此之快，你甚至不應該浪費時間來回答問題。

你真的在告訴我你的問題是需要解決的.01排序問題嗎？

Answer 8

這是一個很好的問題..我解決這個問題的方法是詢問：給定一個項目列表，從列表中選擇兩個連續的項目進行排序的可伸縮性是什麼。隨着清單更加排序，概率將接近100％。

要計算這個概率是比較簡單的：

int sorted = 0; 
for (int i = 0; i < list_length; i++) { 
    if (list[i+1] >= list[i]) { 
     sorted++; 
    } 
} 
sortedness = sorted/(list_length-1); 

我希望這有助於！