关于Array.Sort效率问题
最近好不容易抽出点时间对《华容道》的程序做了番调整，发现程序的性能瓶颈居然在Array.Sort上面！经过调整后，程序运行时间缩短了1秒（河北石家庄李智广编写的华容道全能版V1.1第19关）！
微软的System.Array类提供了一个静态方法Sort，可以很方便的对一维数据进行排序。对于比较懒的我，一向直接使用Array.Sort完成对数组的排序。今天才发现原来Array.Sort存在严重的效率问题。先来看一段使用Array.Sort进行自定义排序的例子。
usingSystem;
usingSystem.Collections;
publicclassDataElement
{
publicintvalue;
publicDataElement(){}
publicDataElement(intvalue){this.value=value;}
}
publicclassDataElementComparer:IComparer
{
publicintCompare(objectx,objecty)
{
return((DataElement)x).value.CompareTo(((DataElement)y).value);
}
}
publicclassClient
{
publicstaticvoidMain()
{
int[]a={5,8,3,6,9};
DataElement[]d=newDataElement[5];
for(inti=0;i<5;i++)
d[i]=newDataElement(a[i]);
Array.Sort(d,newDataElementComparer());
for(inti=0;i<5;i++)
Console.Write(d[i].value+",");
}
}
注意，在上面的例子中，为了实现自定义类（DataElement）的排序，我设计了一个DataElementComparer类，实现了System.Collections.IComparer接口。这样，在应用Array.Sort方法时，同时提供要排序的数组以及DataElementComparer的一个实例，便可以进行排序了。
但需要注意的是，在.net 2003中没有泛型的支持，所以IComparer接口在定义时，Compare方法接收的参数是object类型。因此，在进行比较时需要对值类型数据进行反复Box和UnBox操作，而对于引用类型则反复进行UpCast和DownCast操作，严重影响了效率！
在C# 2.0规范中提供了泛型机制，我想IComparer接口应当重新进行了定义，Array.Sort的效率应当比现在要强很多。我后来将《华容道》中应用Array.Sort的地方改为了使用“快速排序法”代码，效率一下子上去了。解题时间从原来的7.4秒缩短到了6.4秒，可是不小的进步呀！快速排序法代码如下（具体算法可以参考《数据结构》中的相关章节）：
usingSystem;
publicclassDataElement
{
publicintvalue;
publicDataElement(){}
publicDataElement(intvalue){this.value=value;}
}
publicclassQuickSortArray
{
publicDataElement[]list;
publicvoidquickSort()
{
recQuickSort(0,list.Length-1);
}
privatevoidrecQuickSort(intfirst,intlast)
{
intpivotLocation;
if(first<last)
{
pivotLocation=partition(first,last);
recQuickSort(first,pivotLocation-1);
recQuickSort(pivotLocation+1,last);
}
}
privateintpartition(intfirst,intlast)
{
DataElementpivot;
intindex,smallIndex;
swap(first,(first+last)/2);
pivot=list[first];
smallIndex=first;
for(index=first+1;index<=last;index++)
if(list[index].value<pivot.value)
{
smallIndex++;
swap(smallIndex,index);
}
swap(first,smallIndex);
returnsmallIndex;
}
privatevoidswap(intfirst,intsecond)
{
DataElementtemp;
temp=list[first];
list[first]=list[second];
list[second]=temp;
}
}
publicclassClient
{
publicstaticvoidMain()
{
int[]a={42,43,0,1,3,20,31,32,40,41,21,23};
QuickSortArrayqs=newQuickSortArray();
qs.list=newDataElement[12];
for(inti=0;i<12;i++)
qs.list[i]=newDataElement(a[i]);
qs.quickSort();
for(inti=0;i<12;i++)
Console.WriteLine(qs.list[i].value+",");
}
}
优质内容筛选与推荐>>
1、移动端h5实现拍照上传图片并预览&webuploader
2、JS验证手机号
3、[Machine Learning with Python] Familiar with Your Data
4、LeetCode OJ_题解（python）:027-Remove Element 【Array】【Easy】
5、根据table中的tr下标获取值
微软的System.Array类提供了一个静态方法Sort，可以很方便的对一维数据进行排序。对于比较懒的我，一向直接使用Array.Sort完成对数组的排序。今天才发现原来Array.Sort存在严重的效率问题。先来看一段使用Array.Sort进行自定义排序的例子。
usingSystem;usingSystem.Collections;publicclassDataElement{publicintvalue;publicDataElement(){}publicDataElement(intvalue){this.value=value;}}publicclassDataElementComparer:IComparer{publicintCompare(objectx,objecty){return((DataElement)x).value.CompareTo(((DataElement)y).value);}}publicclassClient{publicstaticvoidMain(){int[]a={5,8,3,6,9};DataElement[]d=newDataElement[5];for(inti=0;i<5;i++)d[i]=newDataElement(a[i]);Array.Sort(d,newDataElementComparer());for(inti=0;i<5;i++)Console.Write(d[i].value+",");}}注意，在上面的例子中，为了实现自定义类（DataElement）的排序，我设计了一个DataElementComparer类，实现了System.Collections.IComparer接口。这样，在应用Array.Sort方法时，同时提供要排序的数组以及DataElementComparer的一个实例，便可以进行排序了。
但需要注意的是，在.net 2003中没有泛型的支持，所以IComparer接口在定义时，Compare方法接收的参数是object类型。因此，在进行比较时需要对值类型数据进行反复Box和UnBox操作，而对于引用类型则反复进行UpCast和DownCast操作，严重影响了效率！
在C# 2.0规范中提供了泛型机制，我想IComparer接口应当重新进行了定义，Array.Sort的效率应当比现在要强很多。我后来将《华容道》中应用Array.Sort的地方改为了使用“快速排序法”代码，效率一下子上去了。解题时间从原来的7.4秒缩短到了6.4秒，可是不小的进步呀！快速排序法代码如下（具体算法可以参考《数据结构》中的相关章节）：
usingSystem;publicclassDataElement{publicintvalue;publicDataElement(){}publicDataElement(intvalue){this.value=value;}}publicclassQuickSortArray{publicDataElement[]list;publicvoidquickSort(){recQuickSort(0,list.Length-1);}privatevoidrecQuickSort(intfirst,intlast){intpivotLocation;if(first<last){pivotLocation=partition(first,last);recQuickSort(first,pivotLocation-1);recQuickSort(pivotLocation+1,last);}}privateintpartition(intfirst,intlast){DataElementpivot;intindex,smallIndex;swap(first,(first+last)/2);pivot=list[first];smallIndex=first;for(index=first+1;index<=last;index++)if(list[index].value<pivot.value){smallIndex++;swap(smallIndex,index);}swap(first,smallIndex);returnsmallIndex;}privatevoidswap(intfirst,intsecond){DataElementtemp;temp=list[first];list[first]=list[second];list[second]=temp;}}publicclassClient{publicstaticvoidMain(){int[]a={42,43,0,1,3,20,31,32,40,41,21,23};QuickSortArrayqs=newQuickSortArray();qs.list=newDataElement[12];for(inti=0;i<12;i++)qs.list[i]=newDataElement(a[i]);qs.quickSort();for(inti=0;i<12;i++)Console.WriteLine(qs.list[i].value+",");}}1、移动端h5实现拍照上传图片并预览&webuploader
2、JS验证手机号
3、[Machine Learning with Python] Familiar with Your Data
4、LeetCode OJ_题解（python）:027-Remove Element 【Array】【Easy】
5、根据table中的tr下标获取值