快速排序实现以及时间复杂度分析
【摘要】 原文:http://www.cnblogs.com/fengty90/p/3768827.html
之前只知道快速排序的平均时间复杂度为O(n×log(n)),最糟糕时复杂度为O(n^2),但却不知道具体原因,今天好好证明一下,最后部分摘自《算法导论》。
首先再介绍一遍快排的思想:
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记...
原文:http://www.cnblogs.com/fengty90/p/3768827.html
之前只知道快速排序的平均时间复杂度为O(n×log(n)),最糟糕时复杂度为O(n^2),但却不知道具体原因,今天好好证明一下,最后部分摘自《算法导论》。
首先再介绍一遍快排的思想:
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
文章来源: blog.csdn.net,作者:网奇,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/jacke121/article/details/78145761
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)