C#快速排序
C#快速排序
C#快速排序快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
一、该方法的基本思想是
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
一趟快速排序的算法是
(2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
(3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值a[j],并与key交换;
(4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的a[i],与key交换;
(5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)
二、快速排序算法分析
1、快速排序的时间主要耗费在划分操作上,对长度为k的区间进行划分,共需k-1次关键字的比较。
2、最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)
3、在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:O(nlgn)
4、尽管快速排序的最坏时间为O(n2),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
三、C#快速排序代码
public class QuickSort
{
/// <summary>
/// 排序
/// </summary>
/// <param name="numbers">待排序数组</param>
/// <param name="left">数组第一个元素索引Index</param>
/// <param name="right">数组最后一个元素索引Index</param>
private static void Sort(int[] numbers, int left, int right)
{
//左边索引小于右边,则还未排序完成
if (left < right)
{
//取中间的元素作为比较基准,小于他的往左边移,大于他的往右边移
int middle = numbers[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (numbers[++i] < middle) ;
while (numbers[--j] > middle) ;
if (i >= j)
break;
Swap(numbers, i, j);
}
Sort(numbers, left, i - 1);
Sort(numbers, j + 1, right);
}
}
/// <summary>
/// 交换元素值
/// </summary>
/// <param name="numbers">数组</param>
/// <param name="i">当前左边索引</param>
/// <param name="j">当前右边索引</param>
private static void Swap(int[] numbers, int i, int j)
{
int number = numbers[i];
numbers[i] = numbers[j];
numbers[j] = number;
}
public static void Main()
{
int[] max = { 6, 5, 2, 9, 7, 4, 0 };
Sort(max, 0, max.Length - 1);
StringBuilder temp = new StringBuilder();
for (int i = 0; i < max.Length; i++)
{
temp.Append(max[i].ToString() + ",");
}
Console.WriteLine(temp.ToString().Substring(0, temp.Length - 1));
Console.ReadLine();
}
}
四、下面给出一个简单的排序实例对以上算法进行简单说明
初始数组为--------------> S: 6,10,13,5,8,3,2,11
1、将第一个元素赋值给v----->v = 6;
2、以v为标准将S进行拆分--->[2,5,3],[6],[8,13,10,11] <----------将得到的数组命名为S1, S2;
3、同样对子数组S1进行拆分->[ ], [2], [ 5, 3] <--------------------拆分之后,第一个子数组为空。将得到的数组命名为S12;
4、对子数组S2进行拆分----->[ ], [8], [13, 10, 11]<---------------将得到的数组命名为S22;
5、此时的数组S为---------->2,5,3,6,8,13,10,11
6、对子数组S12进行拆分---->[3], [5],[ ];
7、对自数组S22进行拆分---->[10,11],[13],[]<--------------------将得到的数组命名为S221
8、此时的数组S为----------->2,3,5,6,8,10,11,13
9、对子数组S221进行拆分--->[ ], [11], [13]
10、对后得到的数组为-------->2,3,5,6,8,10,11,13;
- list使用linq排序
- python实现删除列表重复元素功能(Python实现删除排序数组中重复项的两种方法示例)
- dedecms新字段(DEDECMSv5.6 tags.php标签不能按照时间排序的问题)
- C#冒泡排序
- php脚本通过文件路径批量上传文件(php遍历目录下文件并按修改时间排序操作示例)
- 怎么对python中列表进行排序(Python列表常见操作详解获取,增加,删除,修改,排序等)
- sqlserver修改排序规则几种方法(SQL Server 分页编号的另一种方式推荐)
- sql语句按字段排序(SQL语句实现表中字段的组合累加排序)
- mysql 自定义排序
- php排序代码详解(PHP实现数据四舍五入的方法小结4种方法)
- python排序方法简单(快速排序的四种python实现推荐)
- mysql 排序源码(MySQL排序原理和案例详析)
- javascript 经典算法(JavaScript实现的七种排序算法总结推荐!)
- easyUI DataGrid 显示可排序的列
- python教程列表排序(Python一行代码实现快速排序的方法)
- dedecms简短标题(dedecms文章列表实现序列号排序效果实现代码)
- 职场人改不掉这4个习惯,只会越混越穷,一辈子也翻不了身(职场人改不掉这4个习惯)
- 华为 联想等46家公司笔试面试题,涉及各行各业,建议收藏(联想等46家公司笔试面试题)
- ()
- ()
- 800壮士拼死拖住30万日军 八佰 的真实历史,誓与阵地共存亡(800壮士拼死拖住30万日军)
- 演员陈创,火于 哮天犬 ,颠峰于 福贵 ,现状却令人唏嘘(演员陈创火于哮天犬)
热门推荐
- python技巧图解(Python魔法方法功能与用法简介)
- 使用Visual Studio为WebAPI生成帮助文档
- html5canvas案例(h5使用canvas画布实现手势解锁)
- dedecms列表样式修改(dedecms5.7sp1评论添加字段的实现方法)
- mysql的使用步骤(MySQL infobright的安装步骤)
- mysql数据库出现乱码(数据库 MySQL中文乱码解决办法总结)
- centos7docker部署(CentOS 7下设置Docker代理Linux下Systemd服务的环境变量配置)
- 织梦后台卡死怎么办(织梦后台卡死点击栏目无反应导致浏览器崩溃的解决方法)
- opencv人脸识别效果好吗(通过opencv制作人脸识别的窗口)
- mysql随机获取数据