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

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

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

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

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

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

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

    /// <summary>
/// 排序算法类型的接口
/// </summary>
internal interface ISortAlgorithm
{
/// <summary>
/// 按指定的方向对指定的列表进行排序。
/// </summary>
/// <typeparam name="T">要排序的元素的类型</typeparam>
/// <param name="toSort">要排序的列表</param>
/// <param name="direction">排序方向</param>
/// <param name="startIndex">开始索引</param>
/// <param name="endIndex">结束开始索引</param>
/// <param name="compareFunc">比较功能。</param>
void Sort<T>(IList<T> toSort, SortDirection direction, int startIndex, int endIndex, Comparison<T> compareFunc);
}

2.排序算法工厂类:

    /// <summary>
///排序算法工厂类
/// </summary>
internal static class SortAlgorithmFactory
{
/// <summary>
/// 创建排序算法实现。
/// </summary>
/// <param name="algorithm">算法</param>
/// <returns></returns>
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.快速排序算法 :

    /// <summary>
/// 快速排序算法
/// </summary>
internal class QuickSorter : ISortAlgorithm
{
/// <summary>
/// 按指定的方向对指定的列表进行排序。
/// </summary>
/// <typeparam name="T">要排序的元素的类型</typeparam>
/// <param name="toSort">要排序的列表。</param>
/// <param name="direction">在侵权行为中排序元素的方向。</param>
/// <param name="startIndex">开始索引。</param>
/// <param name="endIndex">结束索引。</param>
/// <param name="compareFunc">比较功能。</param>
void ISortAlgorithm.Sort<T>(IList<T> toSort, SortDirection direction, int startIndex, int endIndex, Comparison<T> compareFunc)
{
Func<T, T, bool> valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) < );
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b) > );
break;
default:
throw new ArgumentOutOfRangeException("direction", "Invalid direction specified, can't craete value comparer func");
} PerformSort(toSort, startIndex, endIndex, valueComparerTest);
} /// <summary>
/// 在列表中执行分区的排序,这个例程被递归调用。
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="toSort">排序。</param>
/// <param name="left">左索引。</param>
/// <param name="right">正确的索引。</param>
/// <param name="valueComparerTest">值比较器测试。</param>
private static void PerformSort<T>(IList<T> toSort, int left, int right, Func<T, T, bool> valueComparerTest)
{
while (true)
{
if (right <= left)
{
return;
}
var pivotIndex = Partition(toSort, left, right, left, valueComparerTest);
PerformSort(toSort, left, pivotIndex - , valueComparerTest);
left = pivotIndex + ;
}
} /// <summary>
///分区指定的列表
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="toSort">排序。</param>
/// <param name="left">左边。</param>
/// <param name="right">右边</param>
/// <param name="pivotIndex">枢轴索引。</param>
/// <param name="valueComparerTest">值比较器测试。</param>
/// <returns>新枢纽点的索引</returns>
private static int Partition<T>(IList<T> toSort, int left, int right, int pivotIndex, Func<T, T, bool> 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.希尔排序算法:

    /// <summary>
///希尔排序算法
/// </summary>
internal class ShellSorter : ISortAlgorithm
{
/// <summary>
/// 按指定的方向对指定的列表进行排序。
/// </summary>
/// <typeparam name="T">要排序的元素的类型</typeparam>
/// <param name="toSort">要排序的列表</param>
/// <param name="direction">排序方向</param>
/// <param name="startIndex">开始索引</param>
/// <param name="endIndex">结束开始索引</param>
/// <param name="compareFunc">比较功能。</param>
void ISortAlgorithm.Sort<T>(IList<T> toSort, SortDirection direction, int startIndex, int endIndex, Comparison<T> compareFunc)
{
Func<T, T, bool> valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) > );
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b) < );
break;
default:
throw new ArgumentOutOfRangeException("direction", "Invalid direction specified, can't craete value comparer func");
} int[] increments = { , , , , , , , , , , , , , , , };
for (var incrementIndex = ; 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.选择排序算法:

    /// <summary>
/// 选择排序算法
/// </summary>
internal class SelectionSorter : ISortAlgorithm
{
/// <summary>
/// 按指定的方向对指定的列表进行排序。
/// </summary>
/// <typeparam name="T">要排序的元素的类型</typeparam>
/// <param name="toSort">要排序的列表。</param>
/// <param name="direction">在侵权行为中排序元素的方向。</param>
/// <param name="startIndex">开始索引。</param>
/// <param name="endIndex">结束索引。</param>
/// <param name="compareFunc">比较功能。</param>
void ISortAlgorithm.Sort<T>(IList<T> toSort, SortDirection direction, int startIndex, int endIndex, Comparison<T> compareFunc)
{
Func<T, T, bool> valueComparerTest;
switch (direction)
{
case SortDirection.Ascending:
valueComparerTest = (a, b) => (compareFunc(a, b) > );
break;
case SortDirection.Descending:
valueComparerTest = (a, b) => (compareFunc(a, b) < );
break;
default:
throw new ArgumentOutOfRangeException("direction", "指定的方向无效,无法创建值比较器函数");
} for (var i = startIndex; i < endIndex; i++)
{
var indexValueToSwap = i;
for (var j = i + ; j <= endIndex; j++)
{
if (valueComparerTest(toSort[indexValueToSwap], toSort[j]))
{
indexValueToSwap = j;
}
}
toSort.SwapValues(i, indexValueToSwap);
}
}
}

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

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

简单工厂的UML图如下:

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

最新文章

  1. 使用Keil uVision下载hex文件
  2. Map/Reduce 工作机制分析 --- 数据的流向分析
  3. Django时间查询
  4. zabbix监控系统客户端安装
  5. 【MySQL】Sysbench性能测试
  6. Java多线程——&lt;一&gt;概述、定义任务
  7. Universal-Image-Loader(UIL)使用方法&amp;流程图&amp;源码分析 ----- 未完
  8. JAVA的RSA加密算法工具类
  9. Java串口通信详细解释
  10. (转载)Windows 上搭建Apache FtpServer
  11. Netty SSL安全配置
  12. pinvoke 数据交互笔记
  13. Neuroph开发过程
  14. LVS实现负载均衡原理
  15. Linux 进程后台运行的几种方式 screen
  16. ViewPager防止Fragment销毁以及取消Fragment的预加载
  17. PHP socket 服务器框架集
  18. CS231n课程笔记翻译8:神经网络笔记 part3
  19. 【转】跨DLLnew delete问题
  20. Jboss:The LogManager was not properly installed (you must set the &quot;java.util.logging.manager&quot; system prop

热门文章

  1. *CF2.D(哥德巴赫猜想)
  2. strcpy函数在VS2015无法使用的问题
  3. FIR on Hadoop using hadoop-streaming
  4. VB.net 2010下关联与程序图标设置
  5. sql SYS对象集合
  6. HTML以及CSS的作用和理念
  7. 在一个SQL Server表中的多个列找出最大值
  8. Azure Redis Cache
  9. Understand Lambda Expressions in 3 minutes(翻译)
  10. Silverlight和WPF中DataContractJsonSerializer对时间的处理差异