(3).快速排序算法：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
以上是对算法定义的简单说明，接下来看看算法的具体实现：
1.排序算法类型的接口：
///
/// 排序算法类型的接口
///
internal interface ISortAlgorithm
{
///
/// 按指定的方向对指定的列表进行排序。
///
/// 要排序的元素的类型
/// 要排序的列表
/// 排序方向
/// 开始索引
/// 结束开始索引
/// 比较功能。
void Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc);
}
2.排序算法工厂类：
///
///排序算法工厂类
///
internal static class SortAlgorithmFactory
{
///
/// 创建排序算法实现。
///
/// 算法
///
internal static ISortAlgorithm CreateSortAlgorithmImplementation(SortAlgorithm algorithm)
{
ISortAlgorithm toReturn = null;
switch (algorithm)
{
case SortAlgorithm.SelectionSort:
toReturn = new SelectionSorter();
break;
case SortAlgorithm.ShellSort:
toReturn = new ShellSorter();
break;
case SortAlgorithm.QuickSort:
toReturn = new QuickSorter();
break;
}
return toReturn;
}
}
3.快速排序算法 ：
///
/// 快速排序算法
///
internal class QuickSorter : ISortAlgorithm
{
///
/// 按指定的方向对指定的列表进行排序。
///
/// 要排序的元素的类型
/// 要排序的列表。
/// 在侵权行为中排序元素的方向。
/// 开始索引。
/// 结束索引。
/// 比较功能。
void ISortAlgorithm.Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc)
{
Func valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) < 0);
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b) > 0);
break;
default:
throw new ArgumentOutOfRangeException("direction", "Invalid direction specified, can't craete value comparer func");
}
PerformSort(toSort, startIndex, endIndex, valueComparerTest);
}
///
/// 在列表中执行分区的排序，这个例程被递归调用。
///
///
/// 排序。
/// 左索引。
/// 正确的索引。
/// 值比较器测试。
private static void PerformSort(IList toSort, int left, int right, Func valueComparerTest)
{
while (true)
{
if (right <= left)
{
return;
}
var pivotIndex = Partition(toSort, left, right, left, valueComparerTest);
PerformSort(toSort, left, pivotIndex - 1, valueComparerTest);
left = pivotIndex + 1;
}
}
///
///分区指定的列表
///
///
/// 排序。
/// 左边。
/// 右边
/// 枢轴索引。
/// 值比较器测试。
/// 新枢纽点的索引
private static int Partition(IList toSort, int left, int right, int pivotIndex, Func valueComparerTest)
{
var pivotValue = toSort[pivotIndex];
toSort.SwapValues(pivotIndex, right);
var storeIndex = left;
for (var i = left; i < right; i++)
{
if (!valueComparerTest(toSort[i], pivotValue))
{
continue;
}
toSort.SwapValues(i, storeIndex);
storeIndex++;
}
toSort.SwapValues(storeIndex, right);
return storeIndex;
}
}
4.希尔排序算法：
///
///希尔排序算法
///
internal class ShellSorter : ISortAlgorithm
{
///
/// 按指定的方向对指定的列表进行排序。
///
/// 要排序的元素的类型
/// 要排序的列表
/// 排序方向
/// 开始索引
/// 结束开始索引
/// 比较功能。
void ISortAlgorithm.Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc)
{
Func valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) > 0);
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b) < 0);
break;
default:
throw new ArgumentOutOfRangeException("direction", "Invalid direction specified, can't craete value comparer func");
}
int[] increments = { 1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 };
for (var incrementIndex = 0; incrementIndex < increments.Length; incrementIndex++)
{
for (int intervalIndex = increments[incrementIndex], i = startIndex + intervalIndex; i <= endIndex; i++)
{
var currentValue = toSort[i];
var j = i;
while ((j >= intervalIndex) && valueComparerTest(toSort[j - intervalIndex], currentValue))
{
toSort[j] = toSort[j - intervalIndex];
j -= intervalIndex;
}
toSort[j] = currentValue;
}
}
}
}
5.选择排序算法：
///
/// 选择排序算法
///
internal class SelectionSorter : ISortAlgorithm
{
///
/// 按指定的方向对指定的列表进行排序。
///
/// 要排序的元素的类型
/// 要排序的列表。
/// 在侵权行为中排序元素的方向。
/// 开始索引。
/// 结束索引。
/// 比较功能。
void ISortAlgorithm.Sort(IList toSort, SortDirection direction, int startIndex, int endIndex, Comparison compareFunc)
{
Func valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) > 0);
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b) < 0);
break;
default:
throw new ArgumentOutOfRangeException("direction", "指定的方向无效，无法创建值比较器函数");
}
for (var i = startIndex; i < endIndex; i++)
{
var indexValueToSwap = i;
for (var j = i + 1; j <= endIndex; j++)
{
if (valueComparerTest(toSort[indexValueToSwap], toSort[j]))
{
indexValueToSwap = j;
}
}
toSort.SwapValues(i, indexValueToSwap);
}
}
}
以上的算法实现中，采用了简单工厂模式，实现算法的松耦合。
简单工厂模式是由一个工厂对象决定创建出哪一种产品类的实例。是通过专门定义一个类来负责创建其他类的实例，被创建的实例通常都具有共同的父类。简单工厂模式包含必要的判断逻辑，能够根据外界给定的信息，决定究竟应该创建哪个具体类的对象。
简单工厂的UML图如下：
如果需要增加新的算法，在添加完新的算法实现类后，可直接在工厂方法中添加case分支，无需在客户端更改类，只需要在子类中选择实现类即可。
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
分享名称：DotNet常用排序算法总结-创新互联
当前网址：http://cdweb.net/article/dosddd.html
