【学习分享】小白写算法之冒泡排序篇
【学习分享】小白写算法之冒泡排序篇
前言
最近我要学习下数据结构和算法，有兴趣的小伙伴可以点个关注，一起学习。争取写的浅显易懂。如果你看不懂，那一定是我没学到位。
一、什么是冒泡排序算法
冒泡排序，英文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和2比较，交换。6和1比较，交换。一共交换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,2,1};
printf("冒泡排序前的数组为");
print(arr,6);
bubblesort(arr,6); //调用冒泡算法
printf("\n冒泡排序后的数组为");
print(arr,6);
}
用gcc编译并运行可以得到升序的数组序列，符合预期。
四、冒泡排序复杂度计算
时间复杂度
关于时间复杂度的计算可以看下面这篇文章，浅显易懂。
各位学弟学妹，别再看教材了，时间复杂度看这篇就好了
还是以序列{4,5,6,1,2,3}为例，那么我们一共执行了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)。
五、小结
本文对冒泡排序算法进行了深入浅出的讲解，网上其实有很多大牛写的文章都很不错，都可以相互借鉴学习下。希望大家都能掌握算法真理，码字不易，且行且珍惜~~
原文地址：https://blog.csdn.net/Jason_Yansir/article/details/137271682
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！