减小字体
增大字体- ·上一篇文章：用C#实现插入排序
- ·下一篇文章：C#深度优先遍历结构算法
C#快速排序
：2010-01-28 07:52:00
快速排序思想：
基于分治策略，对冒泡排序的一种改进。对于要排序的一个序列，从中选一值进行排序，将其放入到正确的位置position。然后以position为界，对左右两部分再做排序。直到划分的长度为1。
步骤：设有一待排序的序列
1、分别设置low、high指向序列的最左端、最右端；从序列中选一个进行排序（通常选最左端的值low指向的值），存入到tmp；
2、从high端开始，查找比tmp小的，找到后将该值放入到low指向的存储位中；苯玥igh指向当前查到的值所在的位；
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 = keys as object[];
object[] objArray2 = null;
if (objArray != null)
{
objArray2 = items as object[];
}
if ((objArray != null) && ((items == null) || (objArray2 != null)))
{
new SorterObjectArray(objArray, objArray2, comparer).QuickSort(index, (index + length) - 1);
}
else
{
new SorterGenericArray(keys, items, comparer).QuickSort(index, (index + length) - 1);
}
}
}
C#快速排序
