9
只是一個快速的筆記，這不是作業。我只是試圖刷新我的算法。我與歸併玩弄在C＃中，我已經寫了可以進行排序基於泛型遞歸方法：C＃合併排序性能
class SortAlgorithms
{
public T[] MergeSort<T> (T[] unsortedArray) where T : System.IComparable<T>
{
T[] left, right;
int middle = unsortedArray.Length/2;
left = new T[middle];
right = new T[unsortedArray.Length - middle];
if (unsortedArray.Length <= 1)
return unsortedArray;
for (int i = 0; i < middle; i++)
{
left[i] = unsortedArray[i];
}
for (int i = middle; i < unsortedArray.Length; i++)
{
right[i - middle] = unsortedArray[i];
}
left = MergeSort(left);
right = MergeSort(right);
return Merge<T>(left, right);
}
private T[] Merge<T> (T[] left, T[] right) where T : System.IComparable<T>
{
T[] result = new T[left.Length + right.Length];
int currentElement = 0;
while (left.Length > 0 || right.Length > 0)
{
if (left.Length > 0 && right.Length > 0)
{
if (left[0].CompareTo(right[0]) < 0)
{
result[currentElement] = left[0];
left = left.Skip(1).ToArray();
currentElement++;
}
else
{
result[currentElement] = right[0];
right = right.Skip(1).ToArray();
currentElement++;
}
}
else if (left.Length > 0)
{
result[currentElement] = left[0];
left = left.Skip(1).ToArray();
currentElement++;
}
else if (right.Length > 0)
{
result[currentElement] = right[0];
right = right.Skip(1).ToArray();
currentElement++;
}
}
return result;
}
}
這工作，但它是痛苦的緩慢。我已經使用System.Diagnostic.StopWatch檢查性能與Array.Sort（使用QuickSort算法）來比較我的MergeSort和差異是如此重要，我想知道如果也許我實現這個錯誤。任何意見？
你看過Jons文章嗎？ http://msmvps.com/blogs/jon_skeet/archive/2011/01/06/reimplementing-linq-to-objects-part-26c-optimizing-orderedenumerable.aspx –
你有沒有試過同樣的實現，但沒有泛型？ – pfries
偉大的答案傢伙。對不起，花了這麼長時間纔回應，我一直在重寫代碼，結果代碼看起來幾乎完全像Rafe所建議的。速度快得多，但仍然比原生Array.Sort慢得多。仍在玩一下。 – hobeau