算法实例

# 算法实例 #
----------
##排序算法Sort##
### 快速排序QuickSort ###
*bing搜索结果*
[http://www.bing.com/knows/search?q=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&mkt=zh-cn&FORM=BKACAI](http://www.bing.com/knows/search?q=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&mkt=zh-cn&FORM=BKACAI "快速排序算法QuickSort")


    *个人总结*
    QuickSort排序中其实最贴近人类思考方式的实现是利用队列技术
    1.建立左右队列
    2.遍历List,小于Pivot的放入左队列,大于等于Pivot的放入右队列
    3.左队列出队+Pivot+右队列出队  构造成一个第一次排序的List
    4.左队列重复步骤123,右队列重复123
    5.跳出循环的条件是队列为空
    

----------


    *代码中的算法*
    1.将List尾部的元素設置為pivot
    2.設置一對指針，其中wallIndex指針標誌小於pivot的數,循環指針標誌遍歷的位置
    3.Note:關鍵算法在於List中想要比較移動元素需要兩組指針,wallIndex用於定位需要插入的位置,循環指針用於遍歷元素.
    4.但是以文中算法其實是QuickSort的變種模式,如圖我們如果以List最後的元素作為pivot的話,第一次排序結果因該是{49 38 13 27}49{65 97 76} 但是實際使用的排序算法導致的結果應該為 {49 38 13 27}49{76 65 97}
    5.使用變種的算法優勢在於使用的一對指針,實際減少了內存的使用和交換的開銷
    6.如果使用隊列技術,實際上額外使用了兩塊內存空間,但是其優勢在于可以更加的貼近人類的思維習慣

----------

### 代碼展示 ###

#### 使用指針對 ####
[https://github.com/aalhour/C-Sharp-Algorithms/blob/master/Algorithms/Sorting/QuickSorter.cs](https://github.com/aalhour/C-Sharp-Algorithms/blob/master/Algorithms/Sorting/QuickSorter.cs "代碼來源")
    
    /// <summary>
    /// 
    /// </summary>
    public static class QuickSorter
    {
         
        /// <summary>
        /// The public APIs for the quick sort algorithm.
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="collection"></param>
        /// <param name="comparer"></param>
        public static void QuickSort<T>(this IList<T> collection, Comparer<T> comparer = null)
        {
            int startIndex = 0;
            int endIndex = collection.Count - 1;

            // If the comparer is Null, then initialize it using a default typed comparer
            comparer = comparer ?? Comparer<T>.Default;

            collection.InternalQuickSort(startIndex, endIndex, comparer);
        }

        /// <summary>
        /// The recursive quick sort algorithm
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="collection"></param>
        /// <param name="leftmostIndex"></param>
        /// <param name="rightmostIndex"></param>
        /// <param name="comparer"></param>
        private static void InternalQuickSort<T>(this IList<T> collection, int leftmostIndex, int rightmostIndex, Comparer<T> comparer)
        {
            // Recursive call check
            if (leftmostIndex < rightmostIndex)
            {
                int wallIndex = collection.InternalPartition(leftmostIndex, rightmostIndex, comparer);
                collection.InternalQuickSort(leftmostIndex, wallIndex - 1, comparer);
                collection.InternalQuickSort(wallIndex + 1, rightmostIndex, comparer);
            }
        }

        // The partition function, used in the quick sort algorithm
        /// <summary>
        ///  The partition function, used in the quick sort algorithm
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="collection"></param>
        /// <param name="leftmostIndex"></param>
        /// <param name="rightmostIndex"></param>
        /// <param name="comparer"></param>
        /// <returns></returns>
        private static int InternalPartition<T>(this IList<T> collection, int leftmostIndex, int rightmostIndex, Comparer<T> comparer)
        {
            int wallIndex, pivotIndex;
            
            // Choose the pivot
            pivotIndex = rightmostIndex;
            T pivotValue = collection[pivotIndex];

            // Compare remaining array elements against pivotValue
            wallIndex = leftmostIndex;

            // Loop until pivot: exclusive!
            for (int i = leftmostIndex; i <= (rightmostIndex - 1); i++)
            {
                // check if collection[i] <= pivotValue
                if (comparer.Compare(collection[i], pivotValue) <= 0)
                {
                    collection.Swap(i, wallIndex);
                    wallIndex++;
                }
            }

            collection.Swap(wallIndex, pivotIndex);

            return wallIndex;
        }

    }


#### 使用隊列 ####
    
    /// <summary>
    /// using Queue for quick sort
    /// </summary>
    public static class QuickSorterA
    {
        public static void QuickSortA<T>(this IList<T> collection, Comparer<T> comparer = null)
        {
            // If the comparer is Null, then initialize it using a default typed comparer
            comparer = comparer ?? Comparer<T>.Default;
            Queue<T> _queue = new Queue<T>(collection);
            _queue.InternalQuickSortA(comparer);
            collection.Clear();
            foreach (var item in _queue)
            {
                collection.Add(item);
            }

        }

        private static void InternalQuickSortA<T>(this Queue<T> collection, Comparer<T> comparer)
        {
            if (collection.Count <=0)
            {
                return;
            }
            // Recursive call check
            Queue<T> _leftQueue = new Queue<T>();
            Queue<T> _rightQueue = new Queue<T>();
            T _povit = collection.Dequeue();
            foreach (var item in collection)
            {
                if (comparer.Compare(item, _povit) <= 0)
                {
                    _leftQueue.Enqueue(item);
                }
                else
                {
                    _rightQueue.Enqueue(item);
                }
            }

            _leftQueue.InternalQuickSortA<T>(comparer);
            _rightQueue.InternalQuickSortA<T>(comparer);

            collection.Clear();
            foreach (var item in _leftQueue)
            {
                collection.Enqueue(item);
            }

            collection.Enqueue(_povit);

            foreach (var item in _rightQueue)
            {
                collection.Enqueue(item);
            }
        }
    }

原标题：算法实例

关键词：