排序算法之冒泡排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法之冒泡排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2049字,纯文字阅读大概需要3分钟。
内容图文
冒泡排序的思路:冒泡简单的说,枪打出头鸟,谁最大,就出来排好,就像站队一样,把最高的拎出来站好后,第二高的再拎出来,最后依次排好。
举个例子,有这么一个无序的数组 int arry[10]={2,3,7,9,10,1,6,4,5,8};
冒泡排序会这样做:
第一轮:从arry[0]开始,依次进行比较,谁大就冒出来,比较arr[i]与arr[j+1],如果arr[i]>arr[j+1]则就交换,然后继续往后比,直到最后。
第二轮:由于第一轮已经把最大的冒出了,然后再将剩下的元素重复一轮。
依次类推,可以得出排序好的数组。
示例:
int testarray[10] = {10,9,8,7,6,5,4,3,2,1};
void testMaoPao(int _arry[],int _nLength)
{
if(_nLength<=0)
{
return;
}
for (int i=0;i<_nLength;i++)
{
for (int j=0;j<_nLength-i-1;j++)//主要这一行j的范围,需要-i,是因为需要比对剩下没有排序的元素,-1是因为:假如有10个数,取其中一个数与其他数进行对比,总共比对10-1=9次
{
if (_arry[j]>_arry[j+1])
{
int temp = _arry[j];
_arry[j] = _arry[j+1];
_arry[j + 1] = temp;
}
}
}
}
int main()
{
testMaoPao(testarray,10);
system("pause");
return 0;
}
那既然我们得出了冒泡排序的代码。那还有没有优化的地方呢?我们来想一想
那么代码就变成为如下:
int testarray[10] = { 1,2,3,4,14,6,7,8,9,10};
void testMaoPao(int _arry[],int _nLength)
{
if(_nLength<=0)
{
return;
}
for (int i=0;i<_nLength;i++)
{
bool bFlag = true;//增加标识
for (int j=0;j<_nLength-i-1;j++)
{
if (_arry[j]>_arry[j+1])
{
int temp = _arry[j];
_arry[j] = _arry[j+1];
_arry[j + 1] = temp;
bFlag = false;//如果这一轮中有发生交换的情况,则说明还没排好,继续走下一轮
}
}
if (bFlag)
{
break;//如果发现没有发生交换的情况,则说明排好了,直接退出,后面就不轮询了。
}
}
int mm = 0;
}
int main()
{
testMaoPao(testarray,10);
system("pause");
return 0;
}
说完了代码,我们再来看看时间复杂度:
冒泡排序最坏的情况是:数据是彻底逆序的,每一轮每一步都得交换,比如{10,9,8,7,6,5,4,3,2,1} ,这是最坏的情况,则这种时间复杂度为O(N的平方)。
最好的情况是:数据不需要排序,则按照优化的代码来看,flag从第一轮就为true,则直接退出,时间复杂度为O(N);
那这种排序是不是稳定的呢?
稳定的定义:如果在排序之前,a在b的前面,同时a=b,排序之后a依然在b的前面。
我们来看看:
因为交换的条件是a【j】>a[j+1],那么如果a=b,则永远不会发生交换,a和b的顺序一致不变。
那么冒泡排序是一种稳定的排序。
内容总结
以上是互联网集市为您收集整理的排序算法之冒泡排序全部内容,希望文章能够帮你解决排序算法之冒泡排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。