快速排序(QuickSort)

作者: admin 分类: 算法 发布时间: 2013-02-16 13:28 ė1,756 浏览数 6没有评论
文章转自王牌软件
站长推荐:NSetup一键部署软件
一键式完成美化安装包制作,自动增量升级,数据统计,数字签名。应对各种复杂场景,脚本模块化拆分,常规复杂的脚本代码,图形化设置。无需专业的研发经验,轻松完成项目部署。(www.nsetup.cn)

快速排序(QuickSort)也是一种排序算法,对包含n个数组的输入数组,最坏情况运行时间为O(n^2)。虽然这个最坏情况运行时间比较差,但是快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,期望的运行时间为O(nlgn),且O(nlgn)中隐含的常数因子很小,另外它还能够进行就地排序在虚拟环境中也能很好的工作。

一、快速排序原理

       快速排序也和合并排序一样,基于分治法,分为分解、解决、合并三个步骤;

       分解:数组array[low...high]被分为两个(可能空)子数组array[low...temp-1]和array[temp+1...high],使得array[low...temp-1]中的每一个元素都小于等于array[temp],而array[temp+1...high]中的每一个元素都大于array[temp],下标temp也是在这个过程中被计算出来;

       解决:通过递归的调用快速排序,对子数组array[low...temp-1],array[temp+1...high]进行排序;

       合并:因为两个子数组是就地排序的,将他们的合并不需要操作,整个数组array[low...high]是已经排好序的。

二、快速排序实现

三、快速排序性能分析

       快速排序的运行时间与划分是否对称有关,而后者又与选择了哪一个元素进行划分有关。如果划分是对称的,那么本算法在渐近意义上与合并排序一样快,如果划分是不对称的那么本算法在渐进意义上与插入排序一样慢。下面分别讨论快速排序的最坏情况划分、最家情况划分、平衡的划分。

       最坏情况划分:快速排序的最坏情况划分行为发生在划分过程中产生的两个区域分别包含n-1个元素和0个元素的时候。假设算法每次递归调用都出现了这种不对称划分,划分的时间代价为O(n),因为对一个大小为0的数组进行递归调用后,返回了T(n)=O(1),故算法的运行时间可递归的表示为:

                                                           T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n)

       从直观上来看,如果将每一层递归的代价加起来,就可以得到一个算术级数(等式(array,2)其和值的量极为O(n^2))利用代换法可以比较直接的证明递归式 T(n) = T(n-1) + O(n)的解为 T(n) = O(n^2)。

       因此如果在算法的每一层递归上,划分都是最大程度不对称的,那么算法的运行时间为O(n^2),亦即快速排序算法的最坏情况运行时间不如插入排序的好。此外当输入数组完全排好序时,快速排序的运行时间是O(n^2),而插入排序的运行时间为O(n)。

       最佳情况划分:在Partition可能做的最平衡划分中,得到的两个子问题的大小都不可能大于[n/2],因为若其中一个子问题的大小为[n/2],则另外一个子问题的大小必然为[n/2]-1。在这种情况下,快速排序的运行速度要快得多,这时表达其运行时间的递归式为:

                                                         T(n) <= 2T(n/2) + O(n)     

       解该递归式可得T(n) = O(nlgn)。由于在每一层递归划分的两边都是对称的,因此从渐进意义上来看,算法运行的就更快了。

       平衡的划分: 快速排序的平均情况运行时间与其最佳情况运行时间很接近,而不是非常接近与其最坏情况运行时间(证明原因详细参考《算法导论》原书第二版P88),因为任何一种按常数比例进行划分都会产生深度为O(lgn)的递归树,其中每一层的代价都是O(n),因而每当按照常数比例进行划分时,总的运行时间都是O(nlgn)。


 



只回答业务咨询点击这里给我发消息 点击这里给我发消息

王牌软件,兼职软件设计,软件修改,毕业设计。

本文出自 王牌软件,转载时请注明出处及相应链接。

本文永久链接: http://www.softwareace.cn/?p=172

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">


Ɣ回顶部

无觅相关文章插件,快速提升流量