演算法實例

##排序演算法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

 *使用隊列*
 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

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