气泡排序(Bubble Sort )是计算机科学领域相对简单的排序算法。 这是反复访问要排序的数列，一次比较两个因素，如果他们顺序错了就交换他们。 访问数列的工作反复进行，直到不需要更换为止。 也就是说，那个数列已经排序完毕。 该算法名称的由来是，要素越大，经过交换就会慢慢“漂浮”到数列的顶部。
算法分析
冒泡排序算法是所有排序算法中最简单的，在生活中也应该看到泡沫从水里出来时，越到水面泡沫越大。 在物理上学气压的时候好像也看到过这种现象； 其实，理解冒泡排序可以从这个现象中理解。 每次扫描，大的可以排在后面。 因此，小的也可以排在后面。 因此，每次都可以将无序中最大的(最小的)要素放在无序的最后面)，或者放在有序要素的最前面)。
基本步骤：
外环是遍历每个元素，每次放置一个元素； 内循环是两个比较相邻的元素，较大的元素交换在后面； 如果在第一步循环成功，则表示所有元素都已排序。 代码实现
#includestdio.h //打印数组元素voidprint_array(int*array，int length ) { int index=0； 打印(阵列： (n ) )； for (； 索引长度； 索引() printf('%d，'，* ) * (array索引)； }printf((n(n ) )； }voidbubblesort(intarray[]，int length ) { int i，j，tmp； if(1=length )返回； //判断参数条件for(I=length-1； i 0； (I----) /外部循环，循环各元素for (j=0； j i； j ) ) /内循环、if(array[j]array[j1] )//交换两个相邻元素的tmp=array[j]； array[j]=array[j 1]； array[j 1]=tmp； }}}intmain(void ) ) intarray(12 )={ 1，11，12，4，2，6，9，0，3，7，8，8，2 }； 打印_阵列(array，12 )； bubblesort(Array，12 )； 打印_阵列(array，12 )； 返回0； --------------------------------- -作者：爱心樱桃来源： CSDN原文： https://blog
时间的复杂性
这个时间的复杂性还很容易计算。 外循环和内循环，以及判断和交换要素的时间开销；
最佳情况是指从一开始就确定了顺序，在可以不交换元素的情况下，选择[n(n-1 ) ]/2； 因此，最佳情况的时间复杂度为o(n^2)；
在最坏的情况下，也就是说最初要素是逆序的，所以如果对每个排序交换两个要素，则为[3n(n-1 ) ]/2； (其中，最好的情况花费的时间是交换元素的三个步骤)因此，在最坏的情况下，时间复杂度为o(n^2)；
综上所述：
最佳时间复杂度为o(n ) 2； 有人说O(N )，将这种情况分析如下；
最差的时间复杂度为o(n^2)；
平均时间复杂度为o(n^2)；
空间复杂性
空间复杂性是指交换元素时临时变量所占用的内存空间
最佳空间复杂度，只要起始要素的顺序确定，空间复杂度为0；
最差的空间复杂度是开始元素的逆序排序，空间复杂度是o(n )；
平均空间复杂度为o(1)；
最佳时间复杂度n
很多人说泡沫排序的最佳时间复杂度是o(n )。 实际上，这是判断代码是否使用标志位进行排序，然后修改上面的排序代码。
voidbubblesort(intarray[]，int length ) { int i，j，tmp； int flag=1； if(1=length )返回； for(I=length-1； i 0； I----、flag=1() for ) ) j=0； j i； j () if ) array[j]array[j1] ) { tmp=array[j]； array[j]=array[j 1]； array[j 1]=tmp； flag=0； }if(flag ) break； }如上面的代码所示，如果元素已经排序，则在执行一次循环后立即退出。 或者，元素开始后大致有序，这样可以减少排序次数； 其实，我觉得这个方法也有弊端。 例如，需要在追加的判断下或代入操作
**
空间复杂性为0 **
有人会说可以把这个空间复杂度定为0吧。 由于空间复杂度主要看使用辅助存储器，如果没有辅助存储器变量，则空间复杂度可以说是0，所以该算法中的空间复杂度一般是看交换元素时使用的辅助空间；
a=a b； b=a - b； a=a - b； a=a * b； b=a/b； a=a/b； a=a ^ b； b=a ^ b； a=a ^ b； 以上几种方法可以在不使用临时空间的情况下交换两个要素，但存在越境等潜在问题，所以个人还是坦率地使用临时变量吧。 这样，算法的意图就清楚了。
作者：可爱的樱桃
来源： CSDN
原文： 3359 blog.csdn.net/Yu Zhihui _ no1/article/details/44339711
声明：本文为博主原创文章。 转载请附上博文链接！