【学习分享】小白写算法之冒泡排序篇

前言

最近我要学习下数据结构和算法，有兴趣的小伙伴可以点个关注，一起学习。争取写的浅显易懂。如果你看不懂，那一定是我没学到位。

一、什么是冒泡排序算法

冒泡排序，英文bubblesort，是很容易理解的一种排序方式。想象一下泡泡从水底按顺序冒出就有画面了。

比如原来有一组6位数序列{4,5,6,3,1,2}
按顺序依次从小到大排列，下面的动图演示了冒泡排序算法。

二、冒泡排序算法如何实现

那么如何实现冒泡排序算法呢？
还是以动图数组{4,5,6,3,1,2}为例，需要执行6轮，每1轮（设为第i轮）要把遍历后最大的数冒泡到第(6-i)的位置。

然后看看第i轮冒泡排序做了什么

比如第1轮先把最大数6经过前后比较找了出来，然后把最大数6冒泡到第5的位置。
怎么找到最大数6，通过前后比较，所以是先4和5比较，不需要交换。5和6比较，不需要交换。6和3比较，交换。6和1比较，交换。6和2比较，交换。一共交换5次，结束第1轮。后面每1轮都是执行一样的循环逻辑。

在第i轮的时候，我们用第j位的数和第j+1位的数进行比较，如果第j+1位的数大于第j位的数，那么就互换；否则就不互换，保持原状。

那么关于冒泡排序算法我们已经基本搞清楚了。

三、C语言实现算法

我们设要比较的数组为arr[]
那么用C语言实现冒泡排序算法的代码就可以写出来了。

#include<stdio.h>

void bubblesort(int arr[],int n) //冒泡排序算法
{
   int temp;
    for(int i=0;i<n-1;i++)
        for(int j=0;j<n-i-1;j++)
            if(arr[j]>arr[j+1])  //如果前一个数＞后一个数，那么前后两个数互换
		          {
		            temp = arr[j+1]; 
		            arr[j+1] = arr[j];
		            arr[j] = temp;   
		          }
}

void print(int arr[],int n)  //打印数组
{
	for(int i=0;i<n;i++)
		  printf("%d ",arr[i]);
}

int main()
{
    int arr[6] ={4,5,6,3,1,2};

      printf("冒泡排序前的数组为");
  	  print(arr,6);
      bubblesort(arr,6); //调用冒泡算法
      printf("\n冒泡排序后的数组为");
      print(arr,6);
}

用gcc编译并运行可以得到升序的数组序列，符合预期。

四、复杂度计算

时间复杂度
关于时间复杂度的计算可以看下面这篇文章，浅显易懂。
各位学弟学妹，别再看教材了，时间复杂度看这篇就好了

还是以序列{4,5,6,3,1,2}为例，那么我们一共执行了5+4+3+2+1=15次，推广到n次就是n*(n-1)/2次，那么时间复杂度就是n^2次。
也可以这么理解，c代码中有两个n的嵌套执行语句，那么时间复杂度就是n^2。
记为O(n^2)。

时间复杂度有时候还会考虑最好最坏的情况下的计算，有点超纲了，可以了解下。
冒泡排序最佳情况的时间复杂度，为什么是O(n）
关于最好情况，最坏情况，平均情况复杂度，请参考如下总结文章。
10种排序算法的复杂度，比较，与实现

空间复杂度
关于空间复杂度可以看下面文章
空间复杂度计算超全整理！！（一起手撕复杂度计算）
冒泡排序的空间复杂度怎么计算呢？
在冒泡算法中，我们用到了三个临时变量参数i,j,temp（注意，不是临时的不算在空间复杂度上，所以arr和n不算空间复杂度）

那就很容易理解了，空间复杂度是O(3),一般都记为O(1)。

五、算法稳定性

冒泡排序算法是稳定的吗？首先我们要知道什么是算法稳定性。算法的稳定性是指排序算法在排序过程中能否保持相等的元素的相对顺序。那么很明显冒泡排序在处理两个相同元素的时候是不做处理的，所以冒泡排序算法是稳定的。

六、小结

本文对冒泡排序算法进行了深入浅出的讲解，网上其实有很多大牛写的文章都很不错，都可以相互借鉴学习下。希望大家都能掌握算法真理，码字不易，且行且珍惜~~