算法实例
##排序算法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);
}
}
}測試用例
[TestMethod]
public void TestMethod1()
{
List<long> list = new List<long>() { 23, 42, 4, 16, 8, 15, 3, 9, 55, 0, 34, 12, 2, 46, 25 };
list.QuickSort();
List<long> listA = new List<long>() { 23, 42, 4, 16, 8, 15, 3, 9, 55, 0, 34, 12, 2, 46, 25 };
listA.QuickSortA();
}