我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:全民彩票 > 多级反馈 >

快速排序的时间复杂度

归档日期:06-30       文本归类:多级反馈      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  快速排序每次将待排序数组分为两个部分,在理想状况下,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。

  而在最坏情况下,即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。在实际应用中,快速排序的平均时间复杂度为O(nlogn)。

  快速排序的实现需要消耗递归栈的空间,而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时,对系统栈的频繁存取会影响到排序的效率。

  一种常见的办法是设置一个阈值,在每次递归求解中,如果元素总数不足这个阈值,则放弃快速排序,调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取,节省了时间的消费。

  一般的经验表明,阈值取一个较小的值,排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案:阈值T=10,排序算法用选择排序。

  阈值不要太大,否则省下的存取系统栈的时间,将会被简单排序算法较多的时间花费所抵消。

  另一个可以参考的方法,是自行建栈模拟递归过程。但实际经验表明,收效明显不如设置阈值。

  3.快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”

  随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。

  4.设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

  3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与A[I]交换;

  4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与A[J]交换;

  5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)

  例如:待排序的数组A的值分别是:(初始关键数据:X=49) 注意关键X永远不变,永远是和X进行比较,无论在什么位子,最后的目的就是把X放在中间,小的放前面大的放后面。

  ( 按照算法的第四步从前面开始找X的值,6549,两者交换,此时:I=3 )

  ( 按照算法的第四步从前面开始找大于X的值,9749,两者交换,此时:I=4,J=6 )

  此时再执行第三步的时候就发现I=J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

  快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

  分别对前后两部分进行快速排序 {27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。

  {76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。

本文链接:http://jomsell.com/duojifankui/327.html