我很想找到一種比較排序算法，該算法可以最大限度地減少在算法運行期間每個元素與其他元素進行比較的次數。排序算法最大限度地減少了涉及單個項目的最大比較次數
對於隨機排序的列表，我對兩個分佈感興趣：對列表進行排序所需的比較次數（這是傳統標準）以及列表中每個單個元素的比較次數參與其中。
在比較數量方面表現出色的算法中，比如平均實現O（n log（n）），我想找出一個平均值爲單個元素與其他元素進行比較的次數被最小化。
我認爲理論上的最小值是O（log（n）），它是通過將上圖中的比較總數除以n得到的。
我對數據可能已經在一定程度上已經訂購的情況也感興趣。
也許模擬是尋找答案的最佳方式？
（我以前的問題一直被擱置 - 現在這是一個非常明顯的問題，如果你不能瞭解它，然後請解釋原因）
是你絕對應該做的模擬。
在那裏，你會隱式設置大小和預約約束的方式，可能允許比你提出的一般問題更具體的語句。
還有可以，但是，一般來說這不是一個明確的答案。
Big-O處理漸近行爲，而您的問題 似乎針對較小的問題大小。所以Big-O可以暗示最好的候選人有足夠大的輸入集來進行排序。 （但是，例如，如果您對尺寸< = 5感興趣，結果可能會完全不同！） 爲了獲得對比較操作的正確估計，您需要 來分析每個單獨的算法。
最後，結果（對於給定的算法）必須特定於要排序的數據集。
另外，on avarage在您的上下文中沒有很好定義。我假設你打算參考給定排序的參與對象的比較次數，而不是一個（足夠大）的排序集合上的avarage。
即使在單個算法中，單個對象發生的比較分佈也可能在一種情況下顯示較大的標準偏差，在另一種情況下可能（幾乎）均勻分佈。
由於排序算法的複雜性是由比較的總數（及其位置變化）決定的，所以我不認爲從理論上分析會有助於答案。
也許你可以添加一些背景知道什麼可以使你的問題的答案在實際意義上「有趣」？
程序員stackexchange可能是這個問題的一個更好的地方，請參閱：http：//programmers.stackexchange。com/help/on-topic – nibarius
@rpy：平均而言，我是指長度爲n的列表的預期數量，假設所有初始訂單具有相同的可能性。對於一個具體的例子，你可能想要考慮使用一種算法來提供比較，而真正的人進行比較（例如，圖片/想法之間）;在這種情況下，目標是儘可能減少冗長的比較。 – Gio
@nibarius在提及其他網站時，指出[交叉發佈令人不悅]（http://meta.stackexchange.com/tags/cross-posting/info） – gnat