❤️Python分而治之❤️ 算法图解:第四章:快速排序

举报
是Dream呀 发表于 2022/01/26 23:55:19 2022/01/26
【摘要】 📢📢📢📣📣📣 🌻🌻🌻Hello,大家好我叫是Dream呀,一个有趣的Python博主,小白一枚,多多关照😜😜😜 🏅🏅🏅CSDN Python领域新星创作者,大二在读...

在这里插入图片描述

📢📢📢📣📣📣
🌻🌻🌻Hello,大家好我叫是Dream呀,一个有趣的Python博主,小白一枚,多多关照😜😜😜
🏅🏅🏅CSDN Python领域新星创作者,大二在读,欢迎大家找我合作学习
💕入门须知:这片乐园从不缺乏天才,努力才是你的最终入场券!🚀🚀🚀
💓最后,愿我们都能在看不到的地方闪闪发光,一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤,依然会有Dream,我一直在最温暖的地方等你”,唱的就是我!哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

4.1分而治之

下面我们将探索分而治之——一种著名的递归式问题解决方法。
快速排序是一种排序算法,速度比第二章介绍的选择排序快得多,实属优雅代码的典范。
使用递归函数步骤:
1.找出基线条件
2.每次递归调用都必须离空数组更进一步。
即:缩小问题规模!

编写涉及数组的递归函数条件时,基线条件通常是数组为空或者只包含一个元素。陷入困境时,应该先检查基线条件是不是这样的。

4.2快速排序

快速排序是一种常用的排序算法,比选择排序快得多!
首先,从数组中选择一个元素,这个元素被称为基准值。
然后,找出比基准值小的元素以及比基准值大的元素。
这被称为分区,现在你有:

  1. 一个由小于基准值的数字组成的子数组;
  2. 基准值;
  3. 一个由所有大于基准值的数字助组成的子数组。
    这里进行了分区,得到的两个子数组都是无序的。但如果这两个数组是无序的,对整个数组进行排序将非常容易。

排序步骤:
1.选择基准值;
2.将数组分成两个子数组:小于基准值的元素组成的子数组和大于基准值的元素组成的子数组。
3.对这两个子数组进行快速排序。

# -*-coding:utf-8 -*-
# @Author:到点了,心疼徐哥哥
# 奥利给干!!!
def quicksort(array):
    if len(array)<2:
        return array
    else:
        pivot=array[0]
        less=[i for i in array[1:] if i <= pivot]
        greater=[i for i in array[1:] if i > pivot]
        return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([2,6,5,3,9]))

4.3再谈大O表示法

在这里插入图片描述
这些数据并不准确,这里提供他们的时间只是想让你对时间的差别有大致的认识,实际上,计算机每秒的执行的操作远不止10次。
还有一种名为合并排序的排序算法,其运行时间为O(nlog n),比选择排序快得多!快速排序的情况比较棘手,在最糟糕的情况下,其运行时间为O(n**2)。

4.4总结

1.D&C将问题逐步分解。使用D&C处理列表时,基线条件很可能是空数组或者只包含一个元素的数组。
2.实现快速排序时,请随机选择用作基准值的元素。快速排序的平均运行时间O(nlog n)。
3.大O表示法中的常量有时候事关重大,这就是快速排序比合并排序快的原因所在。
4.比较简单查找和二分查找时,常量几乎无关紧要,因为列表很长时,O(log n)的速度比O(n)快得多!

📢📢📢最后的福利

🍋🍋🍋最后一点小福利带给大家:如果想快速上手python的小伙伴们,这个详细整理PPT可以迅速帮助大家打牢python基础,需要的小伙伴们可以下载一下 Python入门基础教程全套+小白速成+学不会来找我! 🍻🍻🍻
还有自制表白神器,需要自取:
Python表白神器,源码+解析+各种完美配置+浪漫新颖 🍻🍻🍻
在这里插入图片描述

🌲🌲🌲 好啦,这就是今天要分享给大家的全部内容了
❤️❤️❤️如果你喜欢的话,就不要吝惜你的一键三连了~在这里插入图片描述

文章来源: xuyipeng.blog.csdn.net,作者:是Dream呀,版权归原作者所有,如需转载,请联系作者。

原文链接:xuyipeng.blog.csdn.net/article/details/119968572

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。