0°

数据结构和算法-快速排序的随机化和非递归实现

内容预览:
  • 始发于微信公众号: 程序员小乐 上一篇中介绍了  前面一讲介绍的朴...~
  • 解决这种情况,主要在于怎么选取支点~
  • 2)为了减少递归深度,首先对数组更小的一半进行递归,并使用尾调用递归...~

始发于微信公众号: 程序员小乐

数据结构和算法-快速排序的随机化和非递归实现

上一篇中介绍了 


前面一讲介绍的朴素的快速排序的实现,也对其复杂度进行了分析。如果基准(支点 pivot)元素选取的不当,复杂度最坏为O(n^2)。一般有下面的几个优化方法:

1)以上实现使用最后一个元素作为支点。如果输入是已排序的数组,这是一种最坏的情况。解决这种情况,主要在于怎么选取支点。可以随机的选取一个元素作为支点进行划分,或者直接选择最中间的元素,或者选择 第一个元素first、中间元素middle和最后一个元素last 的 中位数。比较常用的是随机化方法。

2)为了减少递归深度,首先对数组更小的一半进行递归,并使用尾调用递归另一半。

3)在数组长度较小时使用插入排序是个不错的选择。例如 的实现是当数组长度小于7时用插入排序。

随机化的实现也比较简单,划分的操作可以继续以最后一个元素为支点,只是先随机的选取一个元素,然后和最后一个元素交换。另外可以把递归的调用,可以改成非递归的,以减少开销。这里直接用数据模拟栈来实现。

完整代码如下:

数据结构和算法-快速排序的随机化和非递归实现

数据结构和算法-快速排序的随机化和非递归实现

数据结构和算法-快速排序的随机化和非递归实现

大家可以可以加群和大牛们(徐宜生、张涛等)一起学习:群二维码如下所示:

数据结构和算法-快速排序的随机化和非递归实现

  • 如果人满了,可以加我的微信,我拉你进群,我的微信二维码:


  • 数据结构和算法-快速排序的随机化和非递归实现


看完本文有收获?请转发分享给更多人

关注「杨守乐」,提升编程技能

数据结构和算法-快速排序的随机化和非递归实现

每当我看到你的点赞、评论、或打赏都会感觉特别激动和高兴,真希望正如你看我的文章一样。我们共同努力。如果您喜欢此文,感觉对您工作有帮助,预期领导会给您涨工资,不妨小额赞助一下,让我有动力继续努力。

赞助方式如下链接:

http://blog.csdn.net/xiaole0313/article/details/52333666


如果您觉得不错,请别忘了分享到您的朋友圈让更多的人看到!! 您的举手之劳,就是对我最好的支持,非常感谢!

版权声明:【我们尊重原创。此篇干货,版权属于原作者。部分文章推送时因种种原因未能与原作者联系上,若涉及版权问题,敬请原作者联系我们,立即处理。】

本文由吧主分享:http://blog.csdn.net/xiaole0313

推荐文章:


【技术群】279126311 [满]

【技术群】484572225 [未]

如果你有好的文章想和大家分享,欢迎投稿,直接向我投递文章链接即可。投稿邮箱:[email protected]

欢迎扫描关注我们的微信公众号(),不要错过每一篇干货~

一键关注我们微信公众号 

以上就是:数据结构和算法-快速排序的随机化和非递归实现 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论