小强今天参加某一线大厂的线上面试。上场和蔼的面试官出了如下一道题目:
小强有点不屑一顾,好歹我也是5年经验的python高级测试开发,居然考简单的冒泡排序,完全体现不出我的水平,待我3秒搞定它。
3分钟后,小强调试成功:
心里颇为得意,大材小用,搞定这个太容易了。
面试官面带笑容,问有没有可以提高效率的地方?
效率?冒泡本来效率就不高啊。
等等。1分钟后小强修改成如下:
面试官皱了一下眉头,问还有其他改进的地方么?
这些倒是把小强惊到了,挠了了头,不好意思的说:“目前只想到这些。”
面试官提示道:“有没有一些循环是没有发生元素交换的?"
小强若有所思,5分钟后修改成如下:
面试官点点头:”恭喜,本题笔试通过!”
冒泡排序用于按升序或降序对列表中的项目进行排序。这是通过比较两个相邻的值来实现的。如果前值比后值高,则两者互换位置。
以如下列表为例:
如果相邻的值都已经排序好,则没有必要继续循环。
排序复杂度用来表示对列表进行排序所需的执行时间和空间。冒泡排序对列表进行(n – 1) 次迭代排序,其中n是列表中元素的总数。
泡沫排序的时间复杂度为O(n2)
空间复杂度衡量对列表进行排序所需的额外空间量。泡沫排序只需要为用于交换值的时间变量提供一个额外空间。因此,它的空间复杂度为O (1)。
页面更新:2024-05-21
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号