c#快速排序类_c#应用
2008-02-23 05:44:00来源:互联网 阅读 ()
快速排序的基本思想是基于分治策略的。对于输入的子序列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
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash