文档章节

DotNet常用排序算法总结

彭泽0902
 彭泽0902
发布于 2016/11/24 18:47
字数 1543
阅读 0
收藏 0
点赞 0
评论 0

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

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

© 著作权归作者所有

共有 人打赏支持
彭泽0902
粉丝 0
博文 44
码字总数 57771
作品 0
武汉
高级程序员
使用SonarCloud对.NET Core项目进行静态代码分析

本文将介绍如何使用SonarCloud进行.NET Core项目的静态代码分析。SonarCloud是SonarQube提供的基于云的版本,特别针对于开源项目是免费的。 首先,在sonarcloud.io创建一个账号,你可以使用G...

dotNET跨平台 ⋅ 05/08 ⋅ 0

Ubuntu 16.04+.Net Core+Docker+Nginx安装部署

前言   最近公司的项目打算移植到.Net Core平台,所以调研了一下.Net Core在Linux下的安装部署。本篇文章会一步步的描述从安装到配置到部署的全部过程。在文章的结构和内容里,笔者借鉴了很...

dotNET跨平台 ⋅ 05/03 ⋅ 0

WPF 使用RPC调用其他进程

如果在 WPF 需要用多进程通信,一个推荐的方法是 WCF ,因为 WCF 是 RPC 计算。先来讲下 RPC (Remote Procedure Call) 远程过程调用,他是通过特定协议,包括 tcp 、http 等对其他进程进行调...

lindexi_gd ⋅ 05/19 ⋅ 0

.NET Core 2.1 RC 1 发布,支持 Alpine Linux 和 ARM

.NET Core 2.1 RC 1 现已发布,官方表示该版本已准备好用于广泛测试和生产环境中使用。 在 Windows, macOS 和 Linux 平台上使用 .NET Core 2.1 RC 1 .NET Core 2.1 RC 1 SDK (includes the ...

局长 ⋅ 05/08 ⋅ 0

ML.NET 0.2 发布,微软的 .NET 跨平台机器学习框架

ML.NET 0.2 已发布,ML.NET 是一个跨平台的开源机器学习框架,旨在让 .NET 开发者更快上手机器学习。 ML.NET 允许 .NET 开发者开发他们自己的模型,并将自定义 ML 注入到他们的应用程序中。他...

局长 ⋅ 06/07 ⋅ 0

Jenkins 使用 Docker 编译发布 .netcore

准备条件: 1,centos,jenkins,docker,docker-compose ps:jenkins我并没有使用docker,因为某些神奇的问题导致我没办法使用docker命令,所有直接装在了宿主机上,docker使用的是 Docker v...

好烟 ⋅ 05/09 ⋅ 0

Asp.net mvc + Redis(准备工作)

今天准备更新这个项目的第二篇博客。有一点需要说明的是之前觉得用的是Asp.net的WebPage,经过查看微软的官方文档还有相关的博客,相比较而言使用起来需要安装一个自动工具WebMatrix可以很快...

有情怀的小猿 ⋅ 05/08 ⋅ 0

Asp.net MVC + Redis(hash入库+log4net集成)

博客四元素 既然要写一个博客类的网站,那就应该知道博客的相关信息。 因为之前有了解过Redis,所以有点纠结于数据的存储方式,最终决定还是按照书上写的一步一步来,搞完了之后再决定是不是...

有情怀的小猿 ⋅ 05/20 ⋅ 0

.NET Core 从 Github到 Nuget 持续集成、部署

一.前言 Nuget 作为一个.NET研发人员,我想你都不会陌生,他为我们提供非常方便的程序包管理,不管是版本,还是包的依赖都能轻松应对,可以说是我们的好助手。而 Nuget 除了官方以外,我们也...

dotNET跨平台 ⋅ 04/20 ⋅ 0

Mac 安装Homebrew 以及brew update

0、前提"安装CocoaPods 因为最近两天我更换了ssd固态硬盘和重装了 macOS Sierra 10.12系统,需要重新安装cocoaPods Xcode8 macOS Sierra 10.12 安装CocoaPods 我在安装过程pod setup遇到问题...

朝雨晚风 ⋅ 2016/12/20 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

【elasticsearch】 随笔 Date datatype

一。时间类型的本质 首先json是没有时间类型的,对于es来说,时间类型的标示可以是下面三种情况 1.一个时间格式的字符串,如:"2014-11-27T08:05:32Z","2015-01-01" or "2015/01/01 12:10:3...

xiaomin0322 ⋅ 29分钟前 ⋅ 0

阿里云资源编排ROS使用教程

阿里云资源编排ROS详细内容: 阿里云资源编排ROS使用教程 资源编排(Resource Orchestration)是一种简单易用的云计算资源管理和自动化运维服务。用户通过模板描述多个云计算资源的依赖关系、...

mcy0425 ⋅ 31分钟前 ⋅ 0

适配器设计模式

1、适配器模式 把一个类的接口变换成客户端所期待的另一种接口 使原本因接口不匹配而无法在一起工作的两个类能够在一起工作 分为类的适配器模式和对象的适配器模式 2、类适配器模式 类的适配...

职业搬砖20年 ⋅ 35分钟前 ⋅ 0

npm操作报错 _stream_writable.js:61

有一天 不知道什么原因(估计和node的版本有关),无论你做什么npm的操作 都会报错/usr/local/lib/node_modules/npm/node_modules/readable-stream/lib/_stream_writable.js:61 这时候只要执...

lilugirl ⋅ 39分钟前 ⋅ 0

Eclipse安装插件的几种方式

Eclipse魅力之一就是支持可扩展的插件,来丰富自身的功能,这种方式也是建立在开源思想之上的。具体使用什么方式去安装插件,要看我们拿到的是什么。 1. 拿到的是一串URL,如http://subclips...

GordonNemo ⋅ 41分钟前 ⋅ 0

div图片叠加

css实现代码如下: <div style="position: relative;"><!--这个层为外面的父层,需设置相对位置样式--> <div style="position: absolute;"><!--子层,需设置绝对位置样式--> <i......

niithub ⋅ 43分钟前 ⋅ 0

作用域slot

如果父组件需要使用子组件中的内容怎么办,比如父组件需要控制子组件的显示 <div id="root"><child><template slot-scope="props"><h1>{{props.item}} <div>编辑</div></h1><......

金于虎 ⋅ 45分钟前 ⋅ 1

HongHu commonservice-eureka 项目构建过程

上一篇我们回顾了关于 spring cloud eureka的相关基础知识,现在我们针对于HongHu cloud的eureka项目做以下构建,整个构建的过程很简单,我会将每一步都构建过程记录下来,希望可以帮助到大家...

明理萝 ⋅ 48分钟前 ⋅ 1

xml和对象的相互转化

@Data//setter和getter方法,toString和equals,hashcode方法@EqualsAndHashCode//代表重写equals和hashcode方法@XmlAccessorType(XmlAccessType.FIELD)public class Classroom {@X......

拐美人 ⋅ 48分钟前 ⋅ 0

tableView cell的高度 分组头部尾部的高度 自适应

@property (nonatomic) CGFloat rowHeight; // default is UITableViewAutomaticDimension@property (nonatomic) CGFloat sectionHeaderHeight; // default is UITableViewA......

娜一片蓝色星海 ⋅ 50分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部