什麼是測試最佳排序算法的雙向鏈表

Question

有人可以推薦我一個排序算法爲我的自定義鏈接列表+例子，基本上它是類似於通用LinkedList，所以如果你可以給通用LinkedList的例子，它將是偉大的。

我打算實施合併排序，請關於優點/缺點，因爲我不太熟悉任何算法，只是採取從谷歌合併排序算法的想法。

C＃示例只如果可能的話:)

乾杯

Answer 1

我在link text

發現了一個不錯的c＃排序實現

Answer 2

這聽起來很像功課。維基百科有一些很好的僞代碼給你開始。

至於哪種算法最好，它取決於內存約束，處理能力，樣本量，數據類型等等。沒有「最好」的算法（雖然算法最糟糕，泡泡排序的人都可以）

Answer 3

Mergesort是一個好主意，因爲與其他高級排序不同，它不需要可索引性（所以它在鏈表上也能正常工作作爲數組）。 C＃中的一般介紹是here - 它不使用泛型，並且無用地引入了數組列表和索引，通過迭代可以很好地處理事情，但是我無法在C＃中找到基本介紹。

所有高級排序算法的一個警告是，在遞歸中最好不要使用「高級算法」，而是切換到更簡單的算法，以獲得更小的子列表 - 簡單的算法更糟糕大O，但乘法常數較小，所以混合通常是最佳的。

一個有價值的變體是natural mergesort，它利用了可能已經存在於數據中的運行 - 我給出的URL使用僞代碼，但它非常易讀。自然合併對於已經大多數已經排序但有幾個項目不按順序的數據是很好的。最後附加 - 當少數項目確實很少時，它可以提供漸近的O（N）性能;-)。