冒泡算法

  1. 云栖社区>
  2. 博客列表>
  3. 正文

冒泡算法

shy丶gril 2016-05-19 09:56:33 浏览331 评论0

摘要: 最近发现冒泡算法还要加个标志位,增加了好多效率啊  思路: 因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。

最近发现冒泡算法还要加个标志位,增加了好多效率啊 

思路:

因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。
若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。

算法:

[cpp] view plain copy
  1. void BubbleSort(SeqList R)  
  2.   { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序  
  3.     int i,j;  
  4.     Boolean exchange; //交换标志  
  5.     for(i=1;i<n;i++){ //最多做n-1趟排序  
  6.       exchange=FALSE; //本趟排序开始前,交换标志应为假  
  7.       for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描  
  8.        if(R[j+1].key<R[j].key){//交换记录  
  9.          R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元  
  10.          R[j+1]=R[j];  
  11.          R[j]=R[0];  
  12.          exchange=TRUE; //发生了交换,故将交换标志置为真  
  13.         }  
  14.       if(!exchange) //本趟排序未发生交换,提前终止算法  
  15.             return;  
  16.     } //endfor(外循环)  
  17.    } //BubbleSort  


时间复杂度分析:

(1)算法的最好时间复杂度
若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:
Cmin=n-1
Mmin=0。
冒泡排序最好的时间复杂度为O(n)。

(2)算法的最坏时间复杂度
若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
Cmax=n(n-1)/2=O(n2)
Mmax=3n(n-1)/2=O(n2)
冒泡排序的最坏时间复杂度为O(n2)。

(3)算法的平均时间复杂度为O(n2)
虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。

(4)算法稳定性
冒泡排序是就地排序,且它是稳定的。


转载:http://blog.csdn.net/xsf50717/article/details/40346927

用云栖社区APP,舒服~

【云栖快讯】直播推荐——现在预约2月28日14:00 VPN网关新品发布会直播,即可赢取SSL-VPN网关一个月免费试用,尽享安全、稳定、快捷的企业级服务!先到先得哦!  详情请点击

网友评论

shy丶gril
文章2084篇 | 关注172
关注
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
基于全网公开发布数据、传播路径和受众群体画像,利用语义分析、情感算法和机器学习,分析公众对品... 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
2017阿里千余份技术干货大盘点

2017阿里千余份技术干货大盘点