冒泡排序算法是算法与数据结构中最基础的排序算法。学会这个算法是有必要,在2010年左右的时候,很多时候面试都会冒泡排序算法。那时候IT行业没现在这么卷,大部分都考察一下冒泡排序就OK了。现在去面试不问个leetcode的hard难度的级别题都不过瘾。那现在有必须在学习冒泡排序吗?当然有必要,基础算法必须掌握,体现你的技术热情,对走技术路线是有绝对的帮助的。
冒泡排序就是排队一样,矮的排前面,高的排后面。
刚开始是乱序的,那就从第一个开始调整,把最高排到后面。排完这个之后,这个位置就被占用。
那再从第一个开始,再找出一个最高的放在倒数第二个位置。
周而复始一直到第一个位置确定好。
发现没有,每个最高的放在最后,然后缩小数组范围,再找出一个高的放在最后。
关键点:
每次都从第一个开始,写代码的时候要注意。
一趟比较后,最后那个位置放最大的数。
除去最后一个位置,再走一趟比较放到倒数第二位置。与第一趟是 一样的,只是范围变窄了。
冒泡排序是稳定的排序, 时间复杂度是o(n^2)
看一个简单例子:
5, 3, 2, 1 一趟冒泡如何进行
第一次比较 :5, 3, 2, 1 ;5和3需要调换位置 : 3, 5, 2, 1 ;
第二次比较 :3, 5, 2, 1 ; 5和2需要调换位置 : 3, 2, 5, 1 ;
第三次比较 :3, 2, 5, 1 ; 5和1需要调换位置 : 3, 2, 1, 5 ;
第一趟排序后,5就到最后的位置。
下面我们一下代码的实现:
def sel_sort(elements) : n = len(elements) for i in range(n): index = i for j in range(i + 1, n): if elements[index] > elements[j]: index = j if index != i : elements[i], elements[index] = elements[index], elements[i] if __name__ == '__main__': arr = [5, 2, 3, 1] sel_sort(arr) print(arr)
运行后输出结果:
[1, 2, 3, 5]
更多内容请关注微信公众号: IT技术漫漫谈
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。