C#排序算法之快速排序
C#排序算法怎样快速排序呢?下面小编为大家整理了C#排序算法之快速排序,希望能帮到大家!
快速排序实现:
复制代码 代码如下:
namespace QuickSort
{
class QuickSort
{
public static void Sort(int[] array)
{
DoSort(array,0, th-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的关系,快速排序又会变的很慢。具体的性能数据后面再来讨论研究。
-
内部排序之堆排序的实现
堆排序(HeapSort)只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。下面小编为大家整理了内部排序之堆排序的实现,希望能帮到大家!(1)基本概念a)堆:设有n个元素的序列:{k1,k2,...,kn}对所有的i=1,2,...,(int)(n/2),当满足下面关系:ki≤k2i,ki≤k2i+1或ki...
-
在VS下如何运行C语言程序
微软后来对VC6.0进行了升级,并更名为VisualStudio(简称VS),支持更多的编程语言,更加强大的功能,不过VisualStudio文件很大,有2~3G左右,大部分功能初学者暂时不会用到;而且安装繁琐,需要将近半个小时的时间,也不容易卸载干净。VisualStudio还有一个缺点是占用资源较多,不...
-
了解什么是编程语言
学习编程语言之前,首先要搞清楚“编程语言”这个概念。下面一起来看看!很小的时候,父母就教我们开口说话,也教我们如何理解别人讲话的意思。经过长时间的熏陶和自我学习,我们竟然在不知不觉中学会了说话,同时也能听懂其他小朋友说话的意思了,我们开始向父母要零花钱...
-
C语言与JAVA的区别
很多人不明白C语言与C++和JAVE之间的区别,为此,为大家收集整理了下面的内容,欢迎阅读!C语言C语言是一门通用计算机编程语言,应用广泛。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语...