只是简单说明一下,这不是家庭作业。我只是想温习我的算法。我正在使用 C# 中的 MergeSort,并且编写了一个可以基于泛型进行排序的递归方法:
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 进行比较,差异如此之大,我想知道我是否实施了错误。任何意见?
我不是一名 C# 程序员,但问题可能出在使用这样的语句吗?
left = left.Skip(1).ToArray();
This might be implemented in a way that forces a deep copy of the underlying array. If so, this would drop the performance of merge from O(n) to O(n2), immediately dropping the performance of the resulting merge sort from O(n log n) to O(n2).
(这是因为重复率从
T(1) = O(1)
T(n) ≤ 2T(n / 2) + O(n)
有解 T(n) = O(n log n),
T(1) = O(1)
T(n) ≤ 2T(n / 2) + O(n2)
which has solution T(n) = O(n2).)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)