C#合并排序性能
发布时间:2020-12-15 04:11:53 所属栏目:百科 来源:网络整理
导读:只是一个快速的笔记,这不是功课.我只是想刷新我的算法.我在C#中使用MergeSort来编写一个可以根据泛型进行排序的递归方法: class SortAlgorithms{ public T[] MergeSortT (T[] unsortedArray) where T : System.IComparableT { T[] left,right; int middle =
只是一个快速的笔记,这不是功课.我只是想刷新我的算法.我在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(); 这可能以强制底层数组的深层副本的方式实现.如果是这样,这会将合并的性能从O(n)降低到O(n2),立即将结果合并排序的性能从O(n log n)降低到O(n2). (这是因为复发变化
其具有T(n)= O(n log n)的解
其具有溶液T(n)= O(n2)) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |