快速排序实现:
namespace quicksort
{
class quicksort
{
public static void sort(int[] array)
{
dosort(array,0, array.length-1);
}
private static void dosort( int[] array, int start, int end)
{
if( start < end)
{
int temp = partition(array, start, end);
dosort(array, start, temp-1);
dosort(array, temp + 1, end);
}
}
private static int partition(int[] array,int start, int end)
{
int index = start - 1;
for( var i=start; i< end; i++)
{
if( array[i] < array[end])
{
index++;
swap(array, index, i);
}
}
swap(array, index +1, end);
return index + 1;
}
private static void swap(int[] array, int index1, int index2)
{
var temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
}
以上即为快速排序的代码,这里有两个重要的方法:
1、partition:该方法是以数组的某个元素为参考元素(轴元素或主元素),将数组划分成三个区域:
【<=参考元素】【参考元素】【>=参考元素】
2. dosort:该方法会调用partition将数组分区,并在新产生的子数组上递归调用最终达到有序的目的。
上面给出的代码是以数组最后一个元素作为参考元素,这仅是参考元素选取的方式之一。我们也可以随即选取数组的元素或者数组中间的元素作为参考元素。事实上参考元素的选取对快速排序的性能有很大影响。如果每次选取的参考元素能将数组分成相对均衡的区域,快速排序将成为最快的排序算法;但在另一种极端情形下,每次分成的数组都是1和n-1的关系,快速排序又会变的很慢。具体的性能数据后面再来讨论研究。
如对本文有疑问,
点击进行留言回复!!
相关文章:
-
-
-
C#实现猜数字游戏
本文实例为大家分享了c#实现猜数字游戏具体代码,供大家参考,具体内容如下给定一个0-100的随机数字猜其大小题目样式:电脑产生一个0到100之间的随机数字,并且...
[阅读全文]
-
-
C# 可空类型的具体使用
在项目中我们经常会遇到可为空类型,那么到底什么是可为空类型呢?下面我们将从4个方面为大家剖析。1、可空类型基础知识顾名思义,可空类型指的就是某个对象类型可以为空...
[阅读全文]
-
-
-
C#实现猜数字小游戏
本文实例为大家分享了c#实现猜数字小游戏的具体代码,供大家参考,具体内容如下效果如图:代码:using system;using system.collecti...
[阅读全文]
-
-
C#实现简单俄罗斯方块
最近在看《.net游戏编程入门经典 c#篇》 第一章介绍了如何制作俄罗斯方块,自己试了试按照书上的步骤,可算是完成了。于是写下这篇文章留作纪念。1.类的设计在充...
[阅读全文]
-
网友评论