DotNet常用排序算法总结

2025-02-24 技术教程

数据结构和算法对一个程序来说是至关重要的，现在介绍一下几种算法，在项目中较为常用的算法有：冒泡排序，简单选择排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序等7中算法。

现在介绍选择排序算法，希尔排序算法，快速排序算法。

(1).选择排序算法：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i(1大于等于i小于等于n)个记录交换。

(2).希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量=1(<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

(3).快速排序算法：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

以上是对算法定义的简单说明，接下来看看算法的具体实现：

1.排序算法类型的接口：

///<summary>///排序算法类型的接口///</summary>internalinterfaceISortAlgorithm{///<summary>///按指定的方向对指定的列表进行排序。///</summary>///<typeparamname="T">要排序的元素的类型</typeparam>///<paramname="toSort">要排序的列表</param>///<paramname="direction">排序方向</param>///<paramname="startIndex">开始索引</param>///<paramname="endIndex">结束开始索引</param>///<paramname="compareFunc">比较功能。</param>voidSort<T>(IList<T>toSort,SortDirectiondirection,intstartIndex,intendIndex,Comparison<T>compareFunc);}

2.排序算法工厂类：

///<summary>///排序算法工厂类///</summary>internalstaticclassSortAlgorithmFactory{///<summary>///创建排序算法实现。///</summary>///<paramname="algorithm">算法</param>///<returns></returns>internalstaticISortAlgorithmCreateSortAlgorithmImplementation(SortAlgorithmalgorithm){ISortAlgorithmtoReturn=null;switch(algorithm){caseSortAlgorithm.SelectionSort:toReturn=newSelectionSorter();break;caseSortAlgorithm.ShellSort:toReturn=newShellSorter();break;caseSortAlgorithm.QuickSort:toReturn=newQuickSorter();break;}returntoReturn;}}

3.快速排序算法：

///<summary>///快速排序算法///</summary>internalclassQuickSorter:ISortAlgorithm{///<summary>///按指定的方向对指定的列表进行排序。///</summary>///<typeparamname="T">要排序的元素的类型</typeparam>///<paramname="toSort">要排序的列表。</param>///<paramname="direction">在侵权行为中排序元素的方向。</param>///<paramname="startIndex">开始索引。</param>///<paramname="endIndex">结束索引。</param>///<paramname="compareFunc">比较功能。</param>voidISortAlgorithm.Sort<T>(IList<T>toSort,SortDirectiondirection,intstartIndex,intendIndex,Comparison<T>compareFunc){Func<T,T,bool>valueComparerTest;switch(direction){caseSortDirection.Ascending:valueComparerTest=(a,b)=>(compareFunc(a,b)<0);break;caseSortDirection.Descending:valueComparerTest=(a,b)=>(compareFunc(a,b)>0);break;default:thrownewArgumentOutOfRangeException("direction","Invaliddirectionspecified,can'tcraetevaluecomparerfunc");}PerformSort(toSort,startIndex,endIndex,valueComparerTest);}///<summary>///在列表中执行分区的排序，这个例程被递归调用。///</summary>///<typeparamname="T"></typeparam>///<paramname="toSort">排序。</param>///<paramname="left">左索引。</param>///<paramname="right">正确的索引。</param>///<paramname="valueComparerTest">值比较器测试。</param>privatestaticvoidPerformSort<T>(IList<T>toSort,intleft,intright,Func<T,T,bool>valueComparerTest){while(true){if(right<=left){return;}varpivotIndex=Partition(toSort,left,right,left,valueComparerTest);PerformSort(toSort,left,pivotIndex-1,valueComparerTest);left=pivotIndex+1;}}///<summary>///分区指定的列表///</summary>///<typeparamname="T"></typeparam>///<paramname="toSort">排序。</param>///<paramname="left">左边。</param>///<paramname="right">右边</param>///<paramname="pivotIndex">枢轴索引。</param>///<paramname="valueComparerTest">值比较器测试。</param>///<returns>新枢纽点的索引</returns>privatestaticintPartition<T>(IList<T>toSort,intleft,intright,intpivotIndex,Func<T,T,bool>valueComparerTest){varpivotValue=toSort[pivotIndex];toSort.SwapValues(pivotIndex,right);varstoreIndex=left;for(vari=left;i<right;i++){if(!valueComparerTest(toSort[i],pivotValue)){continue;}toSort.SwapValues(i,storeIndex);storeIndex++;}toSort.SwapValues(storeIndex,right);returnstoreIndex;}}

4.希尔排序算法：

///<summary>///希尔排序算法///</summary>internalclassShellSorter:ISortAlgorithm{///<summary>///按指定的方向对指定的列表进行排序。///</summary>///<typeparamname="T">要排序的元素的类型</typeparam>///<paramname="toSort">要排序的列表</param>///<paramname="direction">排序方向</param>///<paramname="startIndex">开始索引</param>///<paramname="endIndex">结束开始索引</param>///<paramname="compareFunc">比较功能。</param>voidISortAlgorithm.Sort<T>(IList<T>toSort,SortDirectiondirection,intstartIndex,intendIndex,Comparison<T>compareFunc){Func<T,T,bool>valueComparerTest;switch(direction){caseSortDirection.Ascending:valueComparerTest=(a,b)=>(compareFunc(a,b)>0);break;caseSortDirection.Descending:valueComparerTest=(a,b)=>(compareFunc(a,b)<0);break;default:thrownewArgumentOutOfRangeException("direction","Invaliddirectionspecified,can'tcraetevaluecomparerfunc");}int[]increments={1391376,463792,198768,86961,33936,13776,4592,1968,861,336,112,48,21,7,3,1};for(varincrementIndex=0;incrementIndex<increments.Length;incrementIndex++){for(intintervalIndex=increments[incrementIndex],i=startIndex+intervalIndex;i<=endIndex;i++){varcurrentValue=toSort[i];varj=i;while((j>=intervalIndex)&&valueComparerTest(toSort[j-intervalIndex],currentValue)){toSort[j]=toSort[j-intervalIndex];j-=intervalIndex;}toSort[j]=currentValue;}}}}

5.选择排序算法：

///<summary>///选择排序算法///</summary>internalclassSelectionSorter:ISortAlgorithm{///<summary>///按指定的方向对指定的列表进行排序。///</summary>///<typeparamname="T">要排序的元素的类型</typeparam>///<paramname="toSort">要排序的列表。</param>///<paramname="direction">在侵权行为中排序元素的方向。</param>///<paramname="startIndex">开始索引。</param>///<paramname="endIndex">结束索引。</param>///<paramname="compareFunc">比较功能。</param>voidISortAlgorithm.Sort<T>(IList<T>toSort,SortDirectiondirection,intstartIndex,intendIndex,Comparison<T>compareFunc){Func<T,T,bool>valueComparerTest;switch(direction){caseSortDirection.Ascending:valueComparerTest=(a,b)=>(compareFunc(a,b)>0);break;caseSortDirection.Descending:valueComparerTest=(a,b)=>(compareFunc(a,b)<0);break;default:thrownewArgumentOutOfRangeException("direction","指定的方向无效，无法创建值比较器函数");}for(vari=startIndex;i<endIndex;i++){varindexValueToSwap=i;for(varj=i+1;j<=endIndex;j++){if(valueComparerTest(toSort[indexValueToSwap],toSort[j])){indexValueToSwap=j;}}toSort.SwapValues(i,indexValueToSwap);}}}

以上的算法实现中，采用了简单工厂模式，实现算法的松耦合。

简单工厂模式是由一个工厂对象决定创建出哪一种产品类的实例。是通过专门定义一个类来负责创建其他类的实例，被创建的实例通常都具有共同的父类。简单工厂模式包含必要的判断逻辑，能够根据外界给定的信息，决定究竟应该创建哪个具体类的对象。

简单工厂的UML图如下：

如果需要增加新的算法，在添加完新的算法实现类后，可直接在工厂方法中添加case分支，无需在客户端更改类，只需要在子类中选择实现类即可。