文档章节

DotNet常用排序算法总结

彭泽0902
 彭泽0902
发布于 2016/11/24 18:47
字数 1543
阅读 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
武汉
高级程序员
MEF 插件式开发 - DotNetCore 中强大的 DI

目录 背景叙述 动手实验 注入并设置服务的生命周期 构造函数注入 添加日志记录 总结 相关参考 背景叙述 在前面几篇 MEF 插件式开发 系列博客中,我分别在 和 两种框架下实验了 MEF 的简单实验...

hippieZhou
08/14
0
0
vs2017 编码约定——.editorconfig文件

源码来自:https://docs.microsoft.com/en-us/visualstudio/ide/editorconfig-code-style-settings-reference EditorConfig Visual Studio code style preferences - VS2017中的EditorConfi......

QQZZFT
07/05
0
0
树莓派安装.net core 2.1

0.更新源 sudo apt-get update 1.安装依赖 sudo apt-get install curl libunwind8 gettext 2.下载 SDK 或者 RunTime https://www.microsoft.com/net/download/linux curl -sSL -o dotnet.tar......

蓝曈魅
07/16
0
0
『.NET Core CLI工具文档』(六)dotnet 命令

说明:本文是个人翻译文章,由于个人水平有限,有不对的地方请大家帮忙更正。 原文:dotnet command 翻译:dotnet 命令 名称 dotnet -- 运行命令行命令的一般驱动程序 概要 描述 是命令行界面...

Seay
2016/07/27
0
0
MEF 插件式开发 - DotNetCore 初体验

目录 背景叙述 动手实验 实验1:在 DotNetCore 控制台程序中尝试使用 MEF2 实验2:在 DotNetCore 控制台程序中尝试使用 MEF2 加载外部组件 总结 相关参考 背景叙述 在传统的基于 框架下进行的...

hippieZhou
08/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之JSX(一)

转发 TypeScript基础入门之JSX(一) 介绍 JSX是一种可嵌入的类似XML的语法。 它旨在转换为有效的JavaScript,尽管该转换的语义是特定于实现的。 JSX在React框架中越来越受欢迎,但此后也看到了...

durban
29分钟前
0
0
JavaScript使用原型判断对象类型

1. constructor属性 在JavaScript创建对象(二)——构造函数模式中,我们说过可以使用对象的constructor属性判断对象的类型:p1.constructor === Person,可能当时就有细心的读者会想,我们...

Bob2100
31分钟前
1
0
10-《深度拆解JVM》JVM是怎么实现invokedynamic的?(下)

一、问题引入 上回讲到,为了让所有的动物都能参加赛马,Java 7 引入了 invokedynamic 机制,允许调用任意类的“赛跑”方法。不过,我们并没有讲解 invokedynamic,而是深入地探讨了它所依赖...

飞鱼说编程
51分钟前
2
0
457. Circular Array Loop

Description Difficulty : Medium You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's n......

52iSilence7
今天
1
0
MySQL SQL 常见用法

某字段重复记录 select a.fieldA from tableA a group by a.fieldA having count(a.fieldA)>1;==select * from (select a.fieldA, count(1) as faCount from tableA a group......

园领T
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部