首页 / 算法 / DotNet常用排序算法总结
DotNet常用排序算法总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了DotNet常用排序算法总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含7650字,纯文字阅读大概需要11分钟。
内容图文
![DotNet常用排序算法总结](/upload/InfoBanner/zyjiaocheng/1206/f40cf18da6e54522992fbf8d08e5452a.jpg)
数据结构和算法对一个程序来说是至关重要的,现在介绍一下几种算法,在项目中较为常用的算法有:冒泡排序,简单选择排序,直接插入排序,希尔排序,堆排序,归并排序,快速排序等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) < 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); } /// <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 - 1, valueComparerTest); left = pivotIndex + 1; } } /// <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) > 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.选择排序算法:
/// <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) > 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图如下:
650) this.width=650;" src="/upload/getfiles/default/2022/11/8/20221108040335210.jpg" /> 如果需要增加新的算法,在添加完新的算法实现类后,可直接在工厂方法中添加case分支,无需在客户端更改类,只需要在子类中选择实现类即可。
本文出自 “彭泽0902” 博客,请务必保留此出处http://pengze0902.blog.51cto.com/7693836/1865314
原文:http://pengze0902.blog.51cto.com/7693836/1865314
内容总结
以上是互联网集市为您收集整理的DotNet常用排序算法总结全部内容,希望文章能够帮你解决DotNet常用排序算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。