快速排序思想：
基於分治策略，對冒泡排序的一種改進。對於要排序的一個序列，從中選一值進行排序，將其放入到正確的位置position。然後以position為界，對左右兩部分再做排序。直到劃分的長度為1。
步驟：設有一待排序的序列
1、分別設置low、high指向序列的最左端、最右端；從序列中選一個進行排序（通常選最左端的值low指向的值），存入到tmp；
2、從high端開始，查找比tmp小的，找到後將該值放入到low指向的存儲位中；同時將high指向當前查到的值所在的位；
3、從low端開始，查找比tmp大的，找到後將該值放入到high指向的存儲為中，同時low指向當前查到的值所在位；
4、若low位小於high位，返回步驟2；否則，將tmp值存入到空出來的low+1指向的位置，退出，返回low所在的位置position；
5、以position為界，將序列分成兩部分，分別對兩部分進行排序。
c#實現如下：
//快速排序
public static void QuickSort(int[] items)
{
RecQuickSort(items, 0, items.Length - 1);
}
private static void RecQuickSort(int[] items, int low, int high)
{
if (low < high)
{
int i = Partition(items, low, high);
RecQuickSort(items, low, i - 1);
RecQuickSort(items, i + 1, high);
}
}
private static int Partition(int[] items, int low, int high)
{
int tmp = items[low];
while (low < high)
{
while (low < high && items[high] >= tmp)
high--;
// 換位後不能將low加1,防止跳位
if (low < high)
items[low] = items[high];
while (low < high && items[low] <= tmp)
low++;
if (low < high)
{
items[high] = items[low];
// 有low < high，可將high向前推一位
high--;
}
}
items[low] = tmp;
return low;
}
最關鍵的是Partition,做一次排序的劃分，將其放入到正確的位置。
.NET中的Array.Sort()方法內部使用的就是快速排序算法，看看Array.Sort()方法的實現：
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
public static void Sort(Array array)
{
if (array == null)
{
throw new ArgumentNullException("array");
}
Sort(array, null, array.GetLowerBound(0), array.Length, null);
}
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
{
if (keys == null)
{
throw new ArgumentNullException("keys");
}
if ((keys.Rank != 1) || ((items != null) && (items.Rank != 1)))
{
throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
}
if ((items != null) && (keys.GetLowerBound(0) != items.GetLowerBound(0)))
{
throw new ArgumentException(Environment.GetResourceString("Arg_LowerBoundsMustMatch"));
}
if ((index < keys.GetLowerBound(0)) || (length < 0))
{
throw new ArgumentOutOfRangeException((length < 0) ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
}
if (((keys.Length - (index - keys.GetLowerBound(0))) < length) || ((items != null) && ((index - items.GetLowerBound(0)) > (items.Length - length))))
{
throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
}
if ((length > 1) && (((comparer != Comparer.Default) && (comparer != null)) || !TrySZSort(keys, items, index, (index + length) - 1)))
{
object[] objArray =
