是.NET 4.5反省Array.Sort確定性的實現嗎？

.NET 4.5改變的Array.Sort的實施，以所謂的「內省排序」，這是一個混合算法，其由快速排序，插入排序，並堆排序取決於輸入數據之間進行選擇的。在此詳細介紹：是.NET 4.5反省Array.Sort確定性的實現嗎？

http://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx

這是有據可查的是，排序是「不穩定」，這意味着含有相同的排序順序值可能會或可能不會保留原始輸入順序的兩個元素。但是，我需要知道它是否爲「確定性」，因爲任何任意輸入數據在每次排序時都會以可重複方式返回相同的輸出數據。具體來說，我知道快速排序可以以確定性或非確定性（如果樞軸是隨機選擇的）實現，但我不確定哪些實現用於.NET的內省排序。

從我的測試中，它似乎是確定的，因爲我還沒有看到任何特定數據集運行之間返回不同，但因爲你還沒有看到它顯然你無法證明的東西不只是存在： -/

我想我打算看代碼，以幫助揣摩內省排序是否是確定的，但我希望有人知道這裏的副手，並能拯救我的努力;）

謝謝！瑞安

來源

2014-02-28 user3365745

不，這就是「不穩定」的意思。如果相等比較器的選擇性不夠，那麼任意輸入數據不會以相同的順序重複排序。 –

如果它沒有記錄在算法是確定性的'Array.Sort'頁面上，依賴它是非常危險的。畢竟，你剛看到4.5改變算法。它可以再次改變。 – usr

HansPassant - 我的意思是，在相同的輸入（任意輸入）下，它將以相同的順序重複排序。 @usr - 不幸的是，有人基本上依靠它在4.0中是確定性的，現在我們升級了我們發現的差異。我們想要做的就是編譯4.0版本，然後使用相同的集合來恢復我們所得到的結果，我們只是想確保當我們這樣做時，我們可以依靠與之前相同的排序。換句話說，在4.0確定性中是quicksort實現Array.Sort？ – user3365745

不幸的是，一個人基本上都在 4.0依賴於它是確定性的，而現在我們已經升級我們發現差異。我們想要做的是對編譯4.0和度假村的同一組得到回來我們都拿到，我們只是想確保當我們做，我們可以預先依靠各種各樣是相同的，因爲他們是。換句話說，是否是確定性的4.0 中的快速排序實現Array.Sort？

所以你要找出特定版本Array.Sort是否是確定性的。這是一個更容易的問題。

反編譯.NET BCL代碼（或看看參考源）。如果實施僅使用確定性操作（即，不使用Random），則結果也是確定性的。

最後一次我看到的排序代碼配合到只有幾頁。你會很快篩選它。我的猜測：這顯然是確定性的（如果你的比較器也一樣！）。

來源

2014-02-28 21:20:39 usr

是的你是對的。我會看一看，並用我的發現報告。 – user3365745

經過審查後，排序確實看起來是確定性的。我回顧了排序代碼[這裏]（http://referencesource-beta.microsoft.com/#mscorlib/system/array.cs#c2e31d3cf79aabe2）以及找到類似的SO問題[here]（http： //stackoverflow.com/questions/4035215/how-was-array-sort-implemented-in-net） – user3365745

是.NET 4.5反省Array.Sort確定性的實現嗎？

回答

相關問題