冒泡排序

AI悦创

共 1774字,需浏览 4分钟

 ·

2021-01-07 07:27

你好,我是悦创。


冒泡排序是基础排序。算法采用重复遍历数组并依次比较相邻元素的方法来排序。由于在冒泡算法进行排序的过程中,最大数或者最小数会慢慢“浮”到数组的末尾,所以算法由此命名。



冒泡排序的平均时间复杂度是O(n^2)O(n2),最好情况下的时间复杂度是O(n)O(n), 最坏情况下的时间复杂度是O(n^2)O(n2)。空间复杂度是O(1)O(1)。冒泡排序算法是一个稳定的排序算法。



冒泡排序的过程同样可以用图片说明。我们的目标还是把无序数组以从小到大的顺序排列。



冒泡排序原理

首先,如下图所示,我们从第一个数开始遍历。将第一个数与它后面的元素进行对比,发现后面的元素比它小。

这时候,如图15所示,我们需交换这两个元素的值。

接下来遍历到的是第二个元素。如图16所示,此时第二个元素的值已经变为5。把它和它后方的元素6对比,发现5和6的排列顺序已经是正确的(前面的数小于后面的数),这时候不用进行元素交换,直接继续遍历。

如图17所示,遍历到第三个元素时,发现它比后面的元素更大,这时候就继续交换这两个元素的值。

如图18所示,在类似的一系列操作后,数组中的最大值被交换到了数组中的最后一个(第8个)位置上。

如图19所示,这时候,我们可以确定末尾元素的值是正确的,所以接下来我们只需要对第1-7个位置上的元素再进行遍历了。

在对第1-7个位置上的的元素进行遍历之后,我们可以确定排在第7位的数。同理,在对第1-6个位置上的元素,第1-5个位置上的元素等进行遍历后,我们可以确定数组中排在第6位,第5位的数等。冒泡排序的剩下过程如图20所示。

但是,我们发现,在排好第五个数之后,整个数组的排序就已经完成了,在接下来的遍历中不会再产生元素的交换。这时候,我们可以直接结束遍历。



冒泡排序代码

了解了冒泡排序的流程之后,我们再来看看冒泡排序的代码。

冒泡排序的代码:

nums = [5,3,6,4,1,2,8,7]for i in range(len(nums),0,-1): #更新本趟遍历确定的元素位置    flag = 0        #flag用于标记是否有元素交换发生    for j in range(i-1): #遍历未排序的数组        if nums[j]>nums[j+1]:            nums[j],nums[j+1] = nums[j+1],nums[j]            flag = 1 #标记存在元素交换    if not flag:         break #如果本趟遍历没有经历元素交换,直接跳出循环         print(nums)
运行程序,输出结果为:
[1,2,3,4,5,6,7,8]

这段冒泡排序的代码中使用了两个for循环。外层for循环中的i代表每一次遍历后确定位置的元素的下标。


变量 flag 用于记录是否有元素交换发生,初始为0,在遍历开始后,一旦两位元素进行交换,它的值就会变为1。


随后,再用一个 for 循环对未排序数组进行遍历。为什么遍历的范围是 range(i-1)?因为未排序数组的最后一个元素下标为 i,而我们在遍历时要同时访问下标为j和 j+1 的元素。把遍历范围设为  range(i-1),访问数组时才不会越界。另一个需要注意的点是交换元素的条件:num[j] > num[j+1]。注意不要把大于号写成大于等于号。当这两个元素相等时,为保留它们的原有相对位置,不要进行交换。如果把运算符写成大于等于号,排序算法的稳定性就被破坏了。


遍历结束后,如果flag的值仍然是0,那么说明在整一次遍历中没有元素交换发生,也就是说,所有元素都是有序排列的。这时候就可以直接跳出循环,节省时间。


小结

初级排序算法至此结束了。掌握了初级排序算法之后,我们再进入高级排序算法的学习。

长按识别下方二维码,和众多位岛民一起

把别人的顿悟,变成你的基本功


 花半秒钟就看透事物本质的人,
  和花一辈子都看不清的人,
  注定是截然不同的命运。

浏览 33
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报