Python中怎么实现冒泡排序

本篇文章给大家分享的是有关Python中怎么实现冒泡排序，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

冒泡排序（Bubble Sort）

冒泡排序算法：对无序表进行多趟地比较交换

每一趟对列表两两相邻元素进行比较，大的往后放，这样在所有元素比较完之后，当前列表的最大项就放到了末尾。然后再对前n-1个数据项进行冒泡排序……最终进行n-1趟冒泡排序，整个列表就排序完成（类似于“气泡”上浮过程）

1. 第一趟冒泡：共有n-1对相邻数据进行比较交换

2. 第二趟冒泡：前面的n-1个数据项进行比较交换，共有n-2对相邻数据项进行比较交换

……

3. 直到第n-1趟冒泡排序：最小项一定就在列表的首位

故总共要进行n-1趟冒泡排序

每进行一次冒泡排序后，就少了一个待比较元素。冒泡排序可不会从0次开始，是从1次开始到n-1次。最后一次冒泡只有两个元素，比较交换后就直接可以结束了

 

对于冒泡排序而言，无论无序表中数据项如何排列，算法过程总是需要进行n-1趟冒泡排序。随着趟数增加，比对次数从n-1次减少到1次，故比对次数是1+2+3+……+n-1

（1/2）*n^2 - （1/2）*n

比对时间复杂度：O(n^2)

交换次数最好情况：交换次数为0（已经排序好了）

交换次数最坏情况：交换次数n-1次（每次比较都要交换）

交换时间复杂度：O(n^2)

故冒泡排序算法的时间复杂度：O(n^2)

 

小结：冒泡排序算法是时间复杂度比较差的一类算法，但有一点优势——冒泡排序不占任何额外存储空间

 

前言：虽然做了改进，但依然没有改变其时间复杂度

冒泡排序性能的缺陷在于：无论是否需要交换，都要进行比较。其实很多时候这样的比较是无意义的

若在某一趟冒泡排序中没有发生任何交换意味着什么？意味着已经排序好了，不用再进行后面的冒泡排序了。反之，只要进行了一次交换，则后面就要再进行一次冒泡排序

以上就是Python中怎么实现冒泡排序，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。