Python中怎么实现快速排序
今天就跟大家聊聊有关Python中怎么实现快速排序,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。
创新互联公司为客户提供专业的成都网站建设、做网站、程序、域名、空间一条龙服务,提供基于WEB的系统开发. 服务项目涵盖了网页设计、网站程序开发、WEB系统开发、微信二次开发、手机网站制作等网站方面业务。
快速排序(Quick Sort)
归并排序的思路:分裂再合并,在合并的过程中完成排序
快速排序的思路:分拣再分裂
依据一个“中值”数据项,将数据表分成两半,小于中值的一半和大于中值的一半,然后每个部分递归地进行快速排序
如果希望左右两个部分的数据项个数相同,则应该找到数据表的中位数,然而找到中位数需要付出大量的计算开销,通常选择将第一个元素作为中值
快速排序代码思路:
设置第一个元素为中值,从第二个元素开始,分好两部分元素
将第一个元素(中值)放到合适的位置
递归三要素:
基本结束条件:数据表仅有一个元素,则代表已经排序好了
缩小规模:根据中值,将数据表分成两部分
调用自身:两部分分别调用自身进行快速排序
将数据表分成两部分的方法:
设置左右标号(left和right),将第一个元素作为中值
左标(left)从第二个元素开始向右移动,碰到比中值大的则停止
右标(right)从末尾开始向左移动,碰到比中值小的则停止
判断左标是否已经超过了右标
若没有,交换左右标所指的数据
若left>right则停止移动,此时right位置就是中值位置,将中值交换到right处
完成分裂的过程其实也就完成了排序的一部分工作,由于while循环要执行结束后才会继续后面的程序(即left和right要停止才会结束),故要先判断是否已经 left>right
算法分析
快速排序过程分为两部分:分裂和移动
分裂过程:若两部分规模相当则时间复杂度O(logn)
移动过程:时间复杂度O(n)
综上所述,快速排序的时间复杂度O(nlogn)
并且快速排序运行过程中不需要额外的存储空间
但是,如果运气不好,中值所在的分裂点过于偏离中部,造成左右两部分数量不平衡,极端情况下,有一部分始终没有数据,这样时间复杂度就退化到了O(n^2)
看完上述内容,你们对Python中怎么实现快速排序有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注创新互联行业资讯频道,感谢大家的支持。
分享文章:Python中怎么实现快速排序
地址分享:http://myzitong.com/article/jcised.html