近一直在研究排序的效率，慢慢的我会写一些自己的心得。
下面的代码是快速排序算法的实现，因为我写的时候考虑比较的重用和结构，所以使用了继承的体系，代码可以对任何一种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的算法中最快的。同样是百万级的数量，相比之下，堆排序要比他慢的多。
