免费的网络会议系统,西安seo网站建设,wordpress 二手市场,wordpress页面代码【学习分享】小白写算法之冒泡排序篇 前言一、什么是冒泡排序算法二、冒泡排序算法如何实现三、C语言实现算法四、复杂度计算五、算法稳定性六、小结 前言
最近我要学习下数据结构和算法#xff0c;有兴趣的小伙伴可以点个关注#xff0c;一起学习。争取写的浅显易懂。如果你… 【学习分享】小白写算法之冒泡排序篇 前言一、什么是冒泡排序算法二、冒泡排序算法如何实现三、C语言实现算法四、复杂度计算五、算法稳定性六、小结 前言
最近我要学习下数据结构和算法有兴趣的小伙伴可以点个关注一起学习。争取写的浅显易懂。如果你看不懂那一定是我没学到位。 一、什么是冒泡排序算法
冒泡排序英文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位的数和第j1位的数进行比较如果第j1位的数大于第j位的数那么就互换否则就不互换保持原状。
那么关于冒泡排序算法我们已经基本搞清楚了。 三、C语言实现算法
我们设要比较的数组为arr[] 那么用C语言实现冒泡排序算法的代码就可以写出来了。
#includestdio.hvoid bubblesort(int arr[],int n) //冒泡排序算法
{int temp;for(int i0;in-1;i)for(int j0;jn-i-1;j)if(arr[j]arr[j1]) //如果前一个数后一个数那么前后两个数互换{temp arr[j1]; arr[j1] arr[j];arr[j] temp; }
}void print(int arr[],int n) //打印数组
{for(int i0;in;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}为例那么我们一共执行了5432115次推广到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)。 五、算法稳定性
冒泡排序算法是稳定的吗首先我们要知道什么是算法稳定性。算法的稳定性是指排序算法在排序过程中能否保持相等的元素的相对顺序。那么很明显冒泡排序在处理两个相同元素的时候是不做处理的所以冒泡排序算法是稳定的。 六、小结
本文对冒泡排序算法进行了深入浅出的讲解网上其实有很多大牛写的文章都很不错都可以相互借鉴学习下。希望大家都能掌握算法真理码字不易且行且珍惜~~
