python排序算法 ——冒泡排序
一、前言
相关知识来自《python算法设计与分析》。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序3种。虽然它们的效率相对于高级排序算法偏低，但是在了解初级排序算法之后，再去学习相对复杂的高级排序算法会容易许多。本文介绍冒泡排序。
二、算法描述
冒泡排序采用重复遍历数组并依次比较相邻元素的方法来排序。由于在冒泡算法进行排序的过程中，最大数/最小数会慢慢“浮”到数组的末尾，所以算法由此命名。
冒泡排序的平均时间复杂度是O(n2)，最好情况下的时间复杂度是O(n)，最坏情况下的时间复杂度是O( n2 )。空间复杂度是O(1)。冒泡排序算法是一个稳定的排序算法。冒泡排序的过程同样可以用图说明。我们的目标还是把无序数组以从小到大的顺序排列。
首先，我们从第一个数开始遍历，如图2-14所示。将第一个数与它后面的元素进行对比，发现后面的元素比它小。
这时，我们需交换这两个元素的值，如图2-15所示。
接下来遍历到的是第二个元素。如图2-16所示，此时第二个元素的值已经变为5。把它和它后方的元素6对比，发现5和6的排列顺序已经是正确的（前面的数小于后面的数），这时候不用交换这两个元素的值，直接继续遍历。
如图2-17所示，遍历到第三个元素时，发现它比后面的元素更大，这时，继续交换这两个元素的值。
如图2-18所示，在类似的一系列操作后，数组中的最大值被交换到了数组中的最后一个（第8个）位置上。
如图2-19所示，我们可以确定末尾元素的值是正确的，所以接下来我们只需要对第1～7个位置上的元素再进行遍历。
在对第1～7个位置上的元素进行遍历之后，我们可以确定排在第7位的数。同理，在对第1～6个位置上的元素、第1～5个位置上的元素等进行遍历后，我们可以确定数组中排在第6位、第5位的数等。冒泡排序的剩下过程如图2-20所示。
但是，我们发现，在排好第5个数之后，整个数组的排序就已经完成了，在接下来的遍历中不会再产生元素的交换。这时，我们可以直接结束遍历。
三、代码实现
了解了冒泡排序的流程之后，我们再来看看冒泡排序的代码。
冒泡排序的代码：
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，那么说明在完整的一次遍历中没有元素交换发生，也就是说，所有元素都是有序排列的。这时就可以直接跳出循环，节省时间。文章来源：https://www.toymoban.com/news/detail-442655.html
总结
以上就是今天要讲的内容，本文介绍了冒泡排序的理论知识和代码实现。冒泡排序的平均时间复杂度是O(n2)，最好情况下的时间复杂度是O(n)，最坏情况下的时间复杂度是O( n2 )。空间复杂度是O(1)。冒泡排序算法是一个稳定的排序算法。文章来源地址https://www.toymoban.com/news/detail-442655.html
到了这里，关于python排序算法 ——冒泡排序（附代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
