注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ocean's blog

平常心——可以寂寞,但不允许空虚

 
 
 

日志

 
 

冒泡排序算法之二  

2009-05-30 15:30:06|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

版权所有,转载请注明:本文出自学与思编程网

前篇冒泡排序的文章中,我们分析了冒泡排序的基本思想,也用C语言实现了该排序算法,但那个代码没有做任何优化处理,本文就来分析一下如何优化它。

从前篇文章的分析我们可以看到,在冒泡排序过程中,每一轮排序都可以把其中一个元素正确的放在其最终所在的位置上,所以我们要对n个元素排序的话,我们最多只需n轮处理(其实是n-1轮,因为既然n-1轮可以找到n-1个元素的正确位置,那么最后那个元素的位置也就唯一确定了)。既然最多只需n轮处理,那么有时是否可以减少几轮处理呢,答案是肯定的。我们可以想象一个极端的例子,比如,待排序的元素本身就已经是按正序排列好了的,这时很显然我们在第一轮处理完成后,就应该发现所有的元素就已经排好序了,我们不必要再进行更多轮的处理了。那么我们怎么才能让代码在一轮处理完成后检查是否已经完成排序了呢?其实很简单,我们只需在代码中添加一个标志变量,让它记录这一轮处理是否发生了元素交换,如果整个一轮都没有交换过元素,也就是没有发现反序的元素,那么当然所有的元素都已经排序好了塞。下面看看改进后的代码,加粗字体为改进部分:

void bubblesort(int a[], int count) //升序

{

int i, j;

int tmp;

int exchanged;

for (i = 0; i < count - 1; i++) {

exchanged = 0;

for (j = 0; j < count - 1; j++) {

if (a[j] > a[j + 1]) {

tmp = a[j];

a[j] = a[j + 1];

a[j + 1] = tmp;

exchanged = 1;

}

}

if (exchanged == 0) { //no exchange

break;

}

}

return;

}

优化后的代码从平均上来说要优于没有优化的,因为在很多情况下,它可以减少外循环的次数,这样算法的平均效率得到了提高。

下面我们再来看看另外一个优化,这次我们来优化内循环,也就是减少每一轮处理的元素个数。

认真看前面的代码,就会发现每一轮我们都处理了n-1个元素,但从冒泡排序基本过程中我们可以看到,每进行一轮处理就多一个已经排序好了的元素,即多一个已经找到正确位置的元素,而且在我们这个整数升序排序的例子中这些已经排好序的元素一定位于数组的尾巴上,那么我们在下一轮处理时就应该可以不管已经找到正确位置的元素了,这样就不用处理它们了,达到了优化目的。看看下面的代码比看文字更容易理解,加粗字体为改动部分,只需改动一行!

void bubblesort(int a[], int count) //升序

{

int i, j;

int tmp;

int exchanged;

for (i = 0; i < count - 1; i++) {

exchanged = 0;

for (j = 0; j < count - 1 - i; j++) {

if (a[j] > a[j + 1]) {

tmp = a[j];

a[j] = a[j + 1];

a[j + 1] = tmp;

exchanged = 1;

}

}

if (exchanged == 0) { //no exchange

break;

}

}

return;

}

  评论这张
 
阅读(66)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017