DotNet常用排序算法總結(jié)

   數(shù)據(jù)結(jié)構(gòu)和算法對(duì)一個(gè)程序來(lái)說(shuō)是至關(guān)重要的，現(xiàn)在介紹一下幾種算法，在項(xiàng)目中較為常用的算法有：冒泡排序，簡(jiǎn)單選擇排序，直接插入排序，希爾排序，堆排序，歸并排序，快速排序等7中算法。

  現(xiàn)在介紹選擇排序算法，希爾排序算法，快速排序算法。

    (1).選擇排序算法：通過(guò)n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選擇出關(guān)鍵字最小的記錄，并和第i(1大于等于i小于等于n)個(gè)記錄交換。

    (2).希爾排序：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量  =1( < …<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?/p>

    (3).快速排序算法：通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

   以上是對(duì)算法定義的簡(jiǎn)單說(shuō)明，接下來(lái)看看算法的具體實(shí)現(xiàn)：

     1.排序算法類(lèi)型的接口：

    /// <summary>
    /// 排序算法類(lèi)型的接口
    /// </summary>
    internal interface ISortAlgorithm
    {
        /// <summary>
        /// 按指定的方向?qū)χ付ǖ牧斜磉M(jìn)行排序。
        /// </summary>
        /// <typeparam name="T">要排序的元素的類(lèi)型</typeparam>
        /// <param name="toSort">要排序的列表</param>
        /// <param name="direction">排序方向</param>
        /// <param name="startIndex">開(kāi)始索引</param>
        /// <param name="endIndex">結(jié)束開(kāi)始索引</param>
        /// <param name="compareFunc">比較功能。</param>
        void Sort<T>(IList<T> toSort, SortDirection direction, int startIndex, int endIndex, Comparison<T> compareFunc);
    }

2.排序算法工廠(chǎng)類(lèi)：

    /// <summary>
    ///排序算法工廠(chǎng)類(lèi)
    /// </summary>
    internal static class SortAlgorithmFactory
    {
        /// <summary>
        /// 創(chuàng)建排序算法實(shí)現(xiàn)。
        /// </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>
        /// 按指定的方向?qū)χ付ǖ牧斜磉M(jìn)行排序。
        /// </summary>
        /// <typeparam name="T">要排序的元素的類(lèi)型</typeparam>
        /// <param name="toSort">要排序的列表。</param>
        /// <param name="direction">在侵權(quán)行為中排序元素的方向。</param>
        /// <param name="startIndex">開(kāi)始索引。</param>
        /// <param name="endIndex">結(jié)束索引。</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>
        /// 在列表中執(zhí)行分區(qū)的排序，這個(gè)例程被遞歸調(diào)用。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="toSort">排序。</param>
        /// <param name="left">左索引。</param>
        /// <param name="right">正確的索引。</param>
        /// <param name="valueComparerTest">值比較器測(cè)試。</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>
        ///分區(qū)指定的列表
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="toSort">排序。</param>
        /// <param name="left">左邊。</param>
        /// <param name="right">右邊</param>
        /// <param name="pivotIndex">樞軸索引。</param>
        /// <param name="valueComparerTest">值比較器測(cè)試。</param>
        /// <returns>新樞紐點(diǎn)的索引</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>
        /// 按指定的方向?qū)χ付ǖ牧斜磉M(jìn)行排序。
        /// </summary>
        /// <typeparam name="T">要排序的元素的類(lèi)型</typeparam>
        /// <param name="toSort">要排序的列表</param>
        /// <param name="direction">排序方向</param>
        /// <param name="startIndex">開(kāi)始索引</param>
        /// <param name="endIndex">結(jié)束開(kāi)始索引</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>
        /// 按指定的方向?qū)χ付ǖ牧斜磉M(jìn)行排序。
        /// </summary>
        /// <typeparam name="T">要排序的元素的類(lèi)型</typeparam>
        /// <param name="toSort">要排序的列表。</param>
        /// <param name="direction">在侵權(quán)行為中排序元素的方向。</param>
        /// <param name="startIndex">開(kāi)始索引。</param>
        /// <param name="endIndex">結(jié)束索引。</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", "指定的方向無(wú)效，無(wú)法創(chuàng)建值比較器函數(shù)");
            }

            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);
            }
        }
    }

    以上的算法實(shí)現(xiàn)中，采用了簡(jiǎn)單工廠(chǎng)模式，實(shí)現(xiàn)算法的松耦合。

     簡(jiǎn)單工廠(chǎng)模式是由一個(gè)工廠(chǎng)對(duì)象決定創(chuàng)建出哪一種產(chǎn)品類(lèi)的實(shí)例。是通過(guò)專(zhuān)門(mén)定義一個(gè)類(lèi)來(lái)負(fù)責(zé)創(chuàng)建其他類(lèi)的實(shí)例，被創(chuàng)建的實(shí)例通常都具有共同的父類(lèi)。簡(jiǎn)單工廠(chǎng)模式包含必要的判斷邏輯，能夠根據(jù)外界給定的信息，決定究竟應(yīng)該創(chuàng)建哪個(gè)具體類(lèi)的對(duì)象。

     簡(jiǎn)單工廠(chǎng)的UML圖如下：

   如果需要增加新的算法，在添加完新的算法實(shí)現(xiàn)類(lèi)后，可直接在工廠(chǎng)方法中添加case分支，無(wú)需在客戶(hù)端更改類(lèi)，只需要在子類(lèi)中選擇實(shí)現(xiàn)類(lèi)即可。