C#排序算法之快速排序
2023-06-13 09:14:24 时间
快速排序实现:
复制代码代码如下:
namespaceQuickSort
{
classQuickSort
{
publicstaticvoidSort(int[]array)
{
DoSort(array,0,array.Length-1);
}
privatestaticvoidDoSort(int[]array,intstart,intend)
{
if(start<end)
{
inttemp=Partition(array,start,end);
DoSort(array,start,temp-1);
DoSort(array,temp+1,end);
}
}
privatestaticintPartition(int[]array,intstart,intend)
{
intindex=start-1;
for(vari=start;i<end;i++)
{
if(array[i]<array[end])
{
index++;
Swap(array,index,i);
}
}
Swap(array,index+1,end);
returnindex+1;
}
privatestaticvoidSwap(int[]array,intindex1,intindex2)
{
vartemp=array[index1];
array[index1]=array[index2];
array[index2]=temp;
}
}
}
以上即为快速排序的代码,这里有两个重要的方法:
1、Partition:该方法是以数组的某个元素为参考元素(轴元素或主元素),将数组划分成三个区域:
【<=参考元素】【参考元素】【>=参考元素】
2.DoSort:该方法会调用Partition将数组分区,并在新产生的子数组上递归调用最终达到有序的目的。
上面给出的代码是以数组最后一个元素作为参考元素,这仅是参考元素选取的方式之一。我们也可以随即选取数组的元素或者数组中间的元素作为参考元素。事实上参考元素的选取对快速排序的性能有很大影响。如果每次选取的参考元素能将数组分成相对均衡的区域,快速排序将成为最快的排序算法;但在另一种极端情形下,每次分成的数组都是1和n-1的关系,快速排序又会变的很慢。具体的性能数据后面再来讨论研究。
相关文章
- C#设计原则——合成复用原则
- C#最短路径算法demo
- c# 递归算法
- c# mysql executenonquery_C#与数据库访问技术总结(八)之ExecuteNonQuery方法
- C#double和decimal数据类型以截断的方式保留指定的小数位数
- C#数据结构与算法揭秘四双向链表
- C#简单快速的json组件fastJSON使用介绍
- c#汉诺塔的递归算法与解析
- 重温C#clr笔记总结
- 解析C#中@符号的几种使用方法详解
- C#多态性的深入理解
- c#实现输出本月的月历
- C#中怎么将一个List转换为只读的
- c#实现sunday算法实例
- c#获取相同概率随机数的算法代码
- c#冒泡排序算法示例
- C#Memcached缓存用法实例详解
- asp.net中c#自定义事件的实现方法详解
- C#可用于登录验证码的四位随机数生成方法
- 基于C#实现的端口扫描器实例代码
- C#WinForm编程获取文件物理路径的方法
- C#算法之关于大牛生小牛的问题