程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> 關於.NET >> DotNet常用排序算法總結,dotnet排序算法

DotNet常用排序算法總結,dotnet排序算法

編輯:關於.NET

DotNet常用排序算法總結,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) < 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分支,無需在客戶端更改類,只需要在子類中選擇實現類即可。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved