近一直在研究排序的效率,慢慢的我会写一些自己的心得。
下面的代码是快速排序算法的实现,因为我写的时候考虑比较的重用和结构,所以使用了继承的体系,代码可以对任何一种object进行排序,只要你提供Sort的依据。
using System; using System.Collections; using System.Diagnostics;
namespace Malei.Math.Sort { /// <summary> /// enum of how to select pivot /// </summary> public enum PivotStyle { First=0, Middle, Last, Random }
/// <summary> /// implemention of quick sort /// </summary> public class QuickSort : CSort { private Random rand = new Random() ; public Random Rand { get { return rand;} set { rand= value;} } private PivotStyle pivotStyle = PivotStyle.Middle; public PivotStyle PivotStyle { get { return pivotStyle;} set { pivotStyle= value;} }
public QuickSort() { }
protected virtual int SelectPivot(int startIndex,int endIndex,IList list) { int index = -1;
if (CheckBounds(list,startIndex,endIndex)) { switch(PivotStyle) { case PivotStyle.First: index = startIndex; break; case PivotStyle.Middle: index = (startIndex+endIndex)/2; break; case PivotStyle.Last: index = endIndex; break; case PivotStyle.Random: index = rand.Next(startIndex,endIndex); break; } }
return index; }
public override void Sort(IList list,int startIndex,int endIndex) { if (startIndex >= endIndex) { return; } else if (startIndex + 1 == endIndex) { if (ItemSorter.Compare(list[startIndex],list[endIndex]) > 0) Swap(list,startIndex,endIndex);
return; } else { int pivotIndex = SelectPivot(startIndex,endIndex,list); object pivot = list[pivotIndex];
Swap (list,startIndex,pivotIndex);
int scanUp = startIndex + 1; int scanDown = endIndex;
do { while ( scanUp <= scanDown && ItemSorter.Compare(list[scanUp],pivot) <= 0) scanUp ++;
while (ItemSorter.Compare(pivot,list[scanDown]) < 0) scanDown --;
if (scanUp < scanDown) { Swap (list,scanUp,scanDown); } } while (scanUp < scanDown);
Swap( list,startIndex,scanDown);
if (startIndex < scanDown) Sort(list,startIndex,scanDown-1);
if (scanDown + 1 < endIndex) Sort(list,scanDown + 1,endIndex); } } }
/// <summary> /// Summary description for Sort. /// </summary> public abstract class CSort { protected IComparer itemSorter = null; public IComparer ItemSorter { get { if (itemSorter == null) itemSorter = new DefaultComparer();
return itemSorter; } set { itemSorter = value;} }
protected virtual bool CheckBounds(IList list,int startIndex,int endIndex) { ///check bounds if (startIndex<0 || startIndex>=list.Count) throw new IndexOutOfRangeException("start index is out of range.");
if (endIndex<0 || endIndex>=list.Count) throw new IndexOutOfRangeException("end index is out of range.");
if (startIndex > endIndex) throw new InvalidOperationException("start index must large than end index.");
return true; }
protected virtual void Swap(IList list,int index1,int index2) { object obj = list[index1]; list[index1] = list[index2]; list[index2] = obj; } public abstract void Sort(IList list,int startIndex,int endIndex); } public class DefaultComparer : IComparer { #region IComparer Members
public int Compare(object x, object y) { int int_x = (int)x; int int_y = (int)y;
return int_x.CompareTo(y); }
#endregion }
}
经过仔细的测试,排序百万级的随机数字耗时在3.7s左右,比较值得一提的是微软在标准的Array.Sort()的实现也是QuickSort,但是它只能对Array类型进行排序,百万级的随机数排序只需要0.5s左右,当然这里面的原因很多,最主要的是我使用了大量的类型封装,这无形中加重了系统的负担,如果牺牲掉Generic特性,我想0.5s也不是太大的问题。
提一句,快速排序是所有复杂度是nlogn的算法中最快的。同样是百万级的数量,相比之下,堆排序要比他慢的多。
[C语言系列]NET 中C#的switch语句的语法 [系统软件]托拽Explore中的文件到VB.net的窗口 [系统软件]Boost库在XP+Visual C++.net中的安装 [常用软件]新配色面板:Paint.Net3.0RC1官方下载 [常用软件]用内建的“Net Meeting”聊天 [VB.NET程序]Henry的VB.NET之旅(三)—共享成员 [VB.NET程序]Henry的VB.NET之旅(二)—构造与析构 [VB.NET程序]Henry的VB.NET之旅(一)—失踪的窗体 [VB.NET程序]在托盘上显示Balloon Tooltip(VB.NET) [VB.NET程序]Henry手记-VB.NET中动态加载Treeview节点(二)
|