算法实例
##排序算法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); } } }