C#快速排序类

C#快速排序类2011-03-25快速排序的基本思想是基于分治策略的。对于输入的子序列ap..ar，如果规模足够小则直接进行排序，否则分三步处理：

分解（Divide）：将输入的序列ap..ar划分成两个非空子序列ap..aq和aq+1..ar，使ap..aq中任一元素的值不大于aq+1..ar中任一元素的值。

递归求解（Conquer）：通过递归对p..aq和aq+1..ar进行排序。

合并（Merge）：由于对分解出的两个子序列的排序是就地进行的，所以在ap..aq和aq+1..ar都排好序后不需要执行任何计算ap..ar就已排好序。

这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。

using System;

namespace VcQuickSort
{
/// <summary>
/// ClassQuickSort 快速排序。
/// 范维肖
/// </summary>
public class QuickSort
{
public QuickSort（）
{
}

private void Swap（ref int i,ref int j）
//swap two integer
{
int t;
t=i;
i=j;
j=t;
}

public void Sort（int [] list,int low,int high）
{
if（high<=low）
{
//only one element in array list
//so it do not need sort
return;
}
else if （high==low+1）
{
//means two elements in array list
//so we just compare them
if（list[low]>list[high]）
{
//exchange them
Swap（ref list[low],ref list[high]）;
return;
}
}
//more than 3 elements in the arrary list
//begin QuickSort
myQuickSort（list,low,high）;
}

public void myQuickSort（int [] list,int low,int high）
{
if（low<high）
{
int pivot=Partition（list,low,high）;
myQuickSort（list,low,pivot-1）;
myQuickSort（list,pivot+1,high）;
}
}

private int Partition（int [] list,int low,int high）
{
//get the pivot of the arrary list
int pivot;
pivot=list[low];
while（low<high）
{
while（low<high && list[high]>=pivot）
{
high--;
}
if（low！=high）
{
Swap（ref list[low],ref list[high]）;
low++;
}
while（low<high && list[low]<=pivot）
{
low++;
}
if（low！=high）
{
Swap（ref list[low],ref list[high]）;
high--;
}
}
return low;
}

}
}

来源：http://www.cnblogs.com/tanghuawei/archive/2006/10/19/533711.html