C#排序算法之快速排序
更新时间:2020年6月25日 11:44 点击:1806
快速排序实现:
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的关系,快速排序又会变的很慢。具体的性能数据后面再来讨论研究。
复制代码 代码如下:
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#中隐式运行CMD命令行窗口的方法
下一篇: c# 钩子学习笔记
相关文章
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
- 这篇文章主要介绍了GOLANG版的冒泡排序和快速排序分享,需要的朋友可以参考下...2020-05-11
- 这篇文章主要介绍了C#快速排序算法,实例分析了C#排序方法的相关技巧,非常具有实用价值,需要的朋友可以参考下...2020-06-25
- c语言实现插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序、希尔排序示例,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言对磁盘文件进行快速排序简单实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了php项目开发中用到的快速排序算法,结合实例形式详细分析了php快速排序的原理与使用方法,需要的朋友可以参考下...2016-07-02
- 这篇文章主要介绍了C#使用委托实现的快速排序算法,实例分析了C#委托机制与快速排序算法的实现技巧,需要的朋友可以参考下...2020-06-25
- 快速排序是一种不稳定排序,这篇文章主要为大家详细介绍了C语言简单实现快速排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了分治快速排序源码,有需要的朋友可以参考一下...2020-04-25
- 这篇文章主要为大家详细介绍了C#排序算法之快速排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-06-25
- 这篇文章主要介绍了C/C++实现快速排序的方法,这几天在找工作,被问到快速排序,结果想不出来快速排序怎么弄的;回来搜索了一下,现在记录下来,方便以后查看。...2020-04-25
- 这篇文章主要介绍了C语言数据结构 快速排序实例详解的相关资料,快速排序采用分治的思想,两边数据进行排序,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C/C++实现快速排序的方法,这几天在找工作,被问到快速排序,结果想不出来快速排序怎么弄的;回来搜索了一下,现在记录下来,方便以后查看...2021-08-13
- 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)...2020-04-25
- 本篇文章是对单链表的快速排序进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)...2020-06-25
- 本篇文章是对使用c语言实现冒泡排序,选择排序,快速排序的代码进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 快速排序在时间复杂度同为O(N*logN)的几种排序方法中效率较高,因而比较常用,接下来这里就来逐步讲解快速排序算法及C#版的实现示例...2020-06-25
- 下面给出的代码是以数组最后一个元素作为参考元素,这仅是参考元素选取的方式之一。...2020-06-25
- 这篇文章主要为大家详细介绍了JavaScript希尔排序、快速排序、归并排序算法,感兴趣的朋友可以参考一下...2016-05-09