数据结构笔记 – 排序算法 优化冒泡排序算法
本文由发表于6年前 | 数据结构与算法 | 暂无评论 |  被围观 5,455 views+

一般的冒泡排序算法一般会进行L->length – 1次外部循环,但是有时候数组在循环到一半时就已经排序好了,但是这时循环还是不断的进行下去,一直做比较操作,尽管没有交换数据,但是做了很多不必要的比较操作。

我们可以在程序中设置一个flag标志位,当发现这一轮中没有交换动作时,就表明该数组是排序好的,这样就可以设置flag为false,退出循环。

#include <stdio.h>    

#define MAXSIZE 100  /* 待排序数组的大小 */

typedef bool Flag;  /* 是否在这一轮循环中有进行数据的交换 */ 

typedef struct
{
	int r[MAXSIZE+1];	/* 待排序数组r,r[0]为哨兵或临时变量 */
	int length;			/* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 优化了的冒泡排序算法 */
void BubbleSort03(SortList *L)
{
	int i,j;
	Flag flag=true;
	int temp;
	/* 如果flag是true说明有数据交换过,否则表明数组已经是顺序的了,退出循环 */
	for(i=1;i<L->length && flag;i++)
	{
		flag=false;
		for(j=L->length;j>i;j--)
		{
			if(L->r[j-1]>L->r[j])
			{
				/* 交换r[j-1]和r[j]的值 */
				temp=L->r[j-1];
				L->r[j-1]=L->r[j];
				L->r[j]=temp;
				flag=true;
			}
		}
	}
}
冒泡排序算法的时间复杂度分析:

最好的情况下,即数组本身是排序好的,这时进行n-1次比较,时间复杂度为O(n);最坏的情况下,即数组是逆序的,需要比较次数为:1+2+3+…+(n-1)=n(n-1)/2,推导出时间复杂度为O(n^2)。

除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/data-structure-notes-sorting-algorithm-bubble-sort-algorithm-optimization.html
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
如果您有更好的原创技术博文或者观点,欢迎投稿:admin@itzhai.com,或者关注订阅左侧浮动面板的微信号订阅IT宅itread)发送消息。
数据结构与算法推荐专题
文章评论
    没有评论
给我留言

有人回复时邮件通知我
数据结构与算法的相关文章
随机文章 本月热门 热评
1 ExtJS根据后台数据动态创建CheckboxGroup的方法 2011/10/2
2 Java Web笔记 – Servlet中的Listener监听器的介绍 常用监听器接口 实现监听器 2011/11/12
3 JavaScript设计模式 源代码 2012/10/21
4 Android中的常用控件之ExpandableListActivity SimpleExpandableListAdapter RatingBar SeekBar 2011/7/13
5 C++语法笔记 – 类与对象 2011/9/3
6 SSI介绍 在项目中使用SSI技术提高服务器解释效率 2011/10/6
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
猜您喜欢
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.