爲什麼.NET排序算法要求比較項目與自己？

我注意到，當使用自定義的IComparer<T>對.NET中的數組進行排序時，會請求比較項目與自身的比較。爲什麼.NET排序算法要求比較項目與自己？

爲什麼會出現這種情況？當然，這是一個微不足道的優化，看看是否要對相同索引進行比較，並假設結果必須爲零？

示例代碼：

class Comparer : IComparer<string> 
{ 
    public int Compare(string x, string y) 
    { 
    Console.WriteLine("{0} vs {1}", x, y); 

    return string.Compare(x, y); 
    } 
} 

static void Main(string[] args) 
{ 
    var values = new[] {"A", "D", "C", "B", "E"}; 

    Array.Sort(values, new Comparer()); 
}

隨着輸出（怪比較標記），因爲的Array.Sort（）算法改了好幾次

A vs C 
A vs E 
C vs E 
A vs C 
D vs C 
C vs E 
C vs B 
C vs C *** 
C vs C *** 
A vs B 
A vs B 
A vs A *** 
A vs B 
A vs A *** 
D vs E 
D vs E 
D vs D *** 
D vs E 
D vs D ***

來源

2012-11-12 stusmith

無法重現，我的輸出： d Vs的 çVS d ÇVs的 B對d B對C^ B對一個 éVS d –

也許添加您正在使用的框架版本。 – rene

我正在得到與問題完全相同的輸出。 – Jon

人報告不同的結果。至少在.NET 4.0和.NET 4.5中，可能在此之前。最新版本從QuickSort切換到Introsort。

由於針對Quicksort非常差的最壞情況行爲O（n^2）的反制措施，您會看到一個被比較的元素。該Wikipedia article for Introsort解釋說得好：

在快速排序，關鍵的操作之一是選擇樞軸：圍繞該列表分區的元素。最簡單的數據透視選擇算法是將列表的第一個或最後一個元素作爲數據透視表，導致排序或接近排序的輸入情況下行爲不佳。 Niklaus Wirth的變體使用中間元素來防止這些事件的發生，對於人爲序列退化爲O（n²）。 3中位數選擇算法採用列表的第一個，中間和最後一個元素的中位數;然而，即使這在許多真實世界的輸入中表現良好，仍然有可能設計出一個3中位數殺手名單，這將導致基於此樞軸選擇技術的快速排序急劇下降。這樣的輸入可能被攻擊者利用，例如通過將這樣的列表發送到因特網服務器以作爲拒絕服務攻擊進行排序。

您正在看到3位數中值選擇算法的副作用。

來源

2012-11-12 13:30:53

爲什麼.NET排序算法要求比較項目與自己？

回答

相關問題