DotNet常用排序算法总结

数据结构和算法对一个程序来说是至关重要的，现在介绍一下几种算法，在项目中较为常用的算法有：冒泡排序，简单选择排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序等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分支，无需在客户端更改类，只需要在子类中选择实现类即可。

巴特西

DotNet常用排序算法总结

最新文章

热门文章